LeetCode 91 Decode Ways

概述

https://leetcode.com/problems/decode-ways

动态规划法

注意 C++ 中 string 越界一位不会报错，会返回 \0。

class Solution {
public:
    vector<int> dp;
    int numDecodings(string s) {
        dp.resize(s.size(), -1);
        return helper(s, 0);
    }
    
    int helper(string& s, int i) {
        if (i >= s.size()) return 1;
        if (s[i] == '0') return 0;
        if (i == s.size() - 1) return 1;
        if (dp[i] != -1) return dp[i];
        if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '6')) {
            dp[i] = helper(s, i+1) + helper(s, i+2);
        } else {
            dp[i] = helper(s, i+1);
        }
        cout << i << " " << dp[i] << endl;
        return dp[i];
    }
};

Links: leetcode-91-decode-ways

未经允许，禁止转载，本文源站链接：https://iamazing.cn/