題目出處

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

難度

medium

題目分類

Array, HashTable

個人範例解法

class Solution {
public:
    int numDecodings(string s) {
        // dp
        int n = s.size();
        if(n <= 0){
            return 0;
        }
        vector<int> dp(n+1);
        dp[n] = 1; // ..... 1
        for(int i=n-1; i>=0 ; i--){
            if(s[i] == '0'){ // invalid case
                dp[i] = 0;
                continue;
            }  
            // default
            dp[i] = dp[i+1];

            // if special case
            int num = stoi(s.substr(i, 2)); // count 2
            // cout << num << endl;
            if( 10 <= num && num <= 26 ){
                dp[i] = dp[i+1] + dp[i+2];
            }
        }

        // for(int i=0; i<n+1; i++)
        //     cout << dp[i] << " ";
        return dp[0];
    }
}

解法重點

此為我的解法，應還有其他解法

這題主要考的是 DP，需要先建立一張表。

• 以一般的 case 而言 (我們一個一個數，應該 dp[i] = dp[i+1])
• 特殊 case 的話，允許我們一次走兩格，所以答案會變成 dp[i] = dp[i+1] + dp[i+2]
• 如果碰到 0 開頭的子字串，表示為非法字串，dp[i] = 0

動態規劃 (Dynamic programming，DP) 可參考：

【演算法筆記 #1】動態規劃 (Dynamic programming，DP)

Reference

• Evolve from recursion to dp