91. Decode Ways

 動規五部曲分別為:

1. 確定dp數組(dp table)以及下標的含義

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

(from 代碼隨想錄)

1. 確定dp數組(dp table)以及下標的含義

dp[i] 表示 s[0..i] 有幾種 decode 方法

2. 確定遞推公式

dp[i] 會跟 s[i] 以及 s[i-1] 有關，如果 s[i-1 .. i] 屬於 10~26 以及 s[i] 不為 0，就會累加。

            if(s[i-1] != '0')

                dp[i] += dp[i-1];

            string tmp = s.substr(i-2, 2);

            if(tmp >= "10" && tmp <= "26")

                dp[i] += dp[i-2];

3. dp數組如何初始化

因為有 dp[i-2] 存在，所以 dp 長度設為 n+1

其中 dp[0], dp[1] 皆為 1 (只有 s[0] == '0' 時不成立)

4. 確定遍歷順序

由左向右

5. 舉例推導dp數組

略

class Solution {

public:

    int numDecodings(string s) {

        if(s.size() == 1) return s[0] != '0';

        vector<int> dp(s.size()+1, 0);

        dp[0] = 1;

       

        if(s[0] != '0') dp[1] = 1;

        for(int i=2; i<=s.size(); i++)

        {

            if(s[i-1] != '0')

                dp[i] += dp[i-1];

            string tmp = s.substr(i-2, 2);

            if(tmp >= "10" && tmp <= "26")

                dp[i] += dp[i-2];

        }

        return dp.back();

    }

};