動態(tài)規(guī)劃。要注意way+=dp[i-1]或dp[i-2]以及way+=1的條件。我看有的人把數(shù)組命名為count的。

public class Solution {public int numDecodings(String s) {// Start typing your Java solution below// DO NOT write main() functionint len = s.length();if (len == 0) return 0;int[] dp = new int[len];for (int i = 0; i < len; i++) {int way = 0;if (s.charAt(i) != '0') {if (i-1 >= 0) {way += dp[i-1];}else {way += 1;}}if (i-1 >= 0 && (s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))) {if (i-2 >= 0) {way += dp[i-2];}else {way+= 1;}}dp[i] = way;}return dp[len-1];} }

第二刷，做繁瑣了

class Solution { public:vector<int> ways;int numDecodings(string s) {if (s.size() == 0)return 0;ways.clear();ways.resize(s.size() + 1);for (int i = 0; i < ways.size(); i++){ways[i] = -1;}return numDecodingsRe(s, 0);}int numDecodingsRe(const string &s, int start){if (ways[start] != -1){return ways[start];}if (start == s.size()){ways[start] = 1;return 1;}if (s[start] < '1' || s[start] > '9'){ways[start] = 0;return 0;}if (start == s.size() - 1){ways[start] = 1;return 1;}if (s[start] == '1'){ways[start] = numDecodingsRe(s, start + 1) + numDecodingsRe(s, start + 2);return ways[start];}if (s[start] == '2' && s[start + 1] <= '6'){ways[start] = numDecodingsRe(s, start + 1) + numDecodingsRe(s, start + 2);return ways[start];}ways[start] = numDecodingsRe(s, start + 1);return ways[start];} };

　　

轉(zhuǎn)載于:https://www.cnblogs.com/lautsie/p/3251130.html

總結(jié)

以上是生活随笔為你收集整理的[leetcode]Decode Ways的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。