數據結構與算法——從遞歸入手一維動態規劃【1】

前言：

簡單記錄對左程云系列算法課程--算法講解066【必備】的學習，這是第一篇。主要提供C++代碼和一些簡單的個人理解，如需要細致講解請移步原視頻。

涉及內容：

斐波那契數列、動態規劃

參考視頻：

左程云--算法講解066【必備】從遞歸入手一維動態規劃

題目列表：

1.Leetcode--509. 斐波那契數

2.Leetcode--983. 最低票價

3.Leetcode--91. 解碼方法

4.Leetcode--639. 解碼方法 II

題目解答：

?1.Leetcode--509. 斐波那契數

題目：

解題思考：

如果使用簡單的遞歸，則會發現會有很多重復的遞歸的計算，所以為了優化，可以使用數組存放每一個 f (n) 對應的值，這樣就可以避免重復計算，這就是記憶化搜索。而遞歸一般可以使用迭代完成，即從頂向下到從底向上，再由于我們計算 f (n) 時我們只需要 f (n - 1) 和 f (n - 2) ，所以我們只需要兩個變量。

小結：看似是斐波那契數列，其實是整個一維動態規劃的思考過程，學會思路比做題更重要。

遞歸 -> 記憶化搜索 -> 迭代 -> 空間優化

三個階段（省去迭代版本）代碼如下。

示例代碼：

①純遞歸

class Solution {
public:int fib(int n) {return func(n);}int func(int n) {if(n == 0) {return 0;}if(n == 1) {return 1;}return func(n - 1) + func(n - 2);}
};

②記憶化

class Solution {
private:vector<int> dp;
public:int fib(int n) {dp.resize(n + 1, -1);return func(n);}int func(int n) {if(n == 0) {return 0;}if(n == 1) {return 1;}if(dp[n] != -1) {return dp[n];}dp[n] = func(n - 1) + func(n - 2);return dp[n]; }
};

③最終優化

class Solution {
public:int fib(int n) {int f0 = 0;int f1 = 1;if (n == 0) { return 0; }if (n == 1) { return 1; }for(int i = 0; i < n - 1; i++){int f = f1 + f0;f0 = f1;f1 = f;}return f1;}
};

?2.Leetcode--983.最低票價

題目：

解題思考：

起初自己寫時想到了從左向右迭代求解，但是始終沒有碼出來，直到后來參考別人代碼才完成從左向右的迭代。狀態方程思路是對的，錯誤在于沒有把非旅游日期的對應最小花費更新，總想著去判斷其是否為旅游日期。示例代碼如下。

而左老師的代碼是從后向左迭代求解的，我個人認為是不如從左向右更加容易理解。示例代碼也如下。都已通過測試。

示例代碼：

①從左向右

class Solution {
private:int lastDay;int dp[366] = {0};
public:int mincostTickets(vector<int>& days, vector<int>& costs) {lastDay = days[days.size() - 1];int index = 0;for(int i = 1; i <= lastDay; i++){if(i == days[index]){int f1 = dp[i - 1] + costs[0];int f2 = (i >= 7 ? dp[i - 7] : 0) + costs[1];int f3 = (i >= 30 ? dp[i - 30] : 0) + costs[2];dp[i] = min(f1, f2);dp[i] = min(dp[i], f3);index++;}else{dp[i] = dp[i - 1];}}return dp[lastDay];}
};

②從右向左

class Solution {
private:int durations[3] = { 1, 7, 30 };
public:int mincostTickets(vector<int>& days, vector<int>& costs) {int n = days.size();vector<int> dp(n + 1, INT_MAX);dp[n] = 0;for(int i = n - 1; i >= 0; i--){for(int k = 0, j = i + 1; k <= 2; k++){while(j < n && days[i] + durations[k] > days[j]){j++;}dp[i] = min(dp[i], costs[k] + dp[j]);}}return dp[0];}
};

?3.Leetcode--91. 解碼方法

題目：

解題思考：

本題其實沒有特別的點，注意一下編碼'0'的判斷即可，按遞歸->記憶化->動態規劃寫就行了。

示例代碼：

①純遞歸（超時）

class Solution {
private:string _s;
public:int numDecodings(string s) {_s = s;return getCount(0);}int getCount(int i) {if(i == _s.size()){return 1;}int ans;if(_s[i] == '0') {ans = 0;}else{ans = getCount(i + 1);if(i + 1 < _s.size() && (_s[i] - '0') * 10 + (_s[i + 1] - '0') <= 26){ans += getCount(i + 2);}}return ans;}};

②記憶化（通過）

class Solution {
private:string _s;vector<int> dp;
public:int numDecodings(string s) {_s = s;int len = s.size();dp.resize(len, -1);return getCount(0);}int getCount(int i) {if(i == _s.size()){return 1;}if(dp[i] != -1){return dp[i];}int ans;if(_s[i] == '0') {ans = 0;}else{ans = getCount(i + 1);if(i + 1 < _s.size() && (_s[i] - '0') * 10 + (_s[i + 1] - '0') <= 26){ans += getCount(i + 2);}}dp[i] = ans;return ans;}};

③動態規劃

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n + 1, -1);dp[n] = 1;for(int i = n - 1; i >= 0; i--){if(s[i] == '0'){dp[i] = 0;}else{dp[i] = dp[i + 1];if(i + 1 < n && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26){dp[i] += dp[i + 2];}}}return dp[0];}
};

④空間優化

class Solution {
public:int numDecodings(string s) {int n = s.size();int next = 1;int nextnext = 0;int cur;for(int i = n - 1; i >= 0; i--){if(s[i] == '0'){cur = 0;}else{cur = next;if(i + 1 < n && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26){cur += nextnext;}}nextnext = next;next = cur;}return next;}
};

?4.Leetcode--639. 解碼方法 II

題目：

解題思考：

本題與上一題類似，無非是討論的情況比較多，這里推薦觀看原視頻，左老師講的非常清晰，我在這里僅提供對應代碼。

示例代碼：

①純遞歸（超時）

class Solution {
private:string _s;int len;long mod = 1e9 + 7;
public:int numDecodings(string s) {_s = s;len = s.size();return (int)getCount(0);}int getCount(int i){if(i == len){return 1;}if(_s[i] == '0'){return 0;}unsigned long long ans = 0;if(_s[i] == '*'){ans = (unsigned long long)9 * getCount(i + 1);}else{ans = getCount(i + 1);}if(i + 1 < len){// num, num// num, *// * , num// * , *if(_s[i] != '*'){//num, num//num, *if(_s[i + 1] != '*'){//num, numif((_s[i] - '0') * 10 + (_s[i + 1] - '0') <= 26){ans += getCount(i + 2);}}else{//num, *if(_s[i] == '1'){ans += (unsigned long long)9 * getCount(i + 2);}if(_s[i] == '2'){ans += (unsigned long long)6 * getCount(i + 2);}}}else{//*, num//*, *if(_s[i + 1] != '*'){//*, numif(_s[i + 1] <= '6'){ans += (unsigned long long)2 * getCount(i + 2);}else{ans += getCount(i + 2);}}else{//*, *ans += (unsigned long long)15 * getCount(i + 2);}}}ans = ans % mod;return ans;}
};

②記憶化

class Solution {
private:string _s;int n;long mod = 1e9 + 7;vector<unsigned long long> dp;
public:int numDecodings(string s) {_s = s;n = s.size();dp.resize(n, -1);return (int)getCount(0);}int getCount(int i){if(i == n){return 1;}if(_s[i] == '0'){return 0;}if(dp[i] != -1){return dp[i];}unsigned long long ans = 0;if(_s[i] == '*'){ans = (unsigned long long)9 * getCount(i + 1);}else{ans = getCount(i + 1);}if(i + 1 < n){// num, num// num, *// * , num// * , *if(_s[i] != '*'){//num, num//num, *if(_s[i + 1] != '*'){//num, numif((_s[i] - '0') * 10 + (_s[i + 1] - '0') <= 26){ans += getCount(i + 2);}}else{//num, *if(_s[i] == '1'){ans += (unsigned long long)9 * getCount(i + 2);}if(_s[i] == '2'){ans += (unsigned long long)6 * getCount(i + 2);}}}else{//*, num//*, *if(_s[i + 1] != '*'){//*, numif(_s[i + 1] <= '6'){ans += (unsigned long long)2 * getCount(i + 2);}else{ans += getCount(i + 2);}}else{//*, *ans += (unsigned long long)15 * getCount(i + 2);}}}ans = ans % mod;dp[i] = ans;return ans;}
};

③動態規劃

class Solution {
private:string _s;int n;long mod = 1e9 + 7;vector<unsigned long long> dp;public:int numDecodings(string s) {_s = s;n = s.size();dp.resize(n + 1, -1);dp[n] = 1;for (int i = n - 1; i >= 0; i--) {if(_s[i] == '0'){dp[i] = 0;continue;}if (_s[i] == '*') {// ans = (unsigned long long)9 * getCount(i + 1);dp[i] = (unsigned long long)9 * dp[i + 1];} else {// ans = getCount(i + 1);dp[i] = dp[i + 1];}if (i + 1 < n) {// num, num// num, *// * , num// * , *if (_s[i] != '*') {// num, num// num, *if (_s[i + 1] != '*') {// num, numif ((_s[i] - '0') * 10 + (_s[i + 1] - '0') <= 26) {// ans += getCount(i + 2);dp[i] += dp[i + 2];}} else {// num, *if (_s[i] == '1') {// ans += (unsigned long long)9 * getCount(i + 2);dp[i] += (unsigned long long)9 * dp[i + 2];}if (_s[i] == '2') {// ans += (unsigned long long)6 * getCount(i + 2);dp[i] += (unsigned long long)6 * dp[i + 2];}}} else {//*, num//*, *if (_s[i + 1] != '*') {//*, numif (_s[i + 1] <= '6') {// ans += (unsigned long long)2 * getCount(i + 2);dp[i] += (unsigned long long)2 * dp[i + 2];} else {// ans += getCount(i + 2);dp[i] += dp[i + 2];}} else {//*, *// ans += (unsigned long long)15 * getCount(i + 2);dp[i] += (unsigned long long)15 * dp[i + 2];}}}dp[i] = dp[i] % mod;}return (int)dp[0];}
};

④空間壓縮

class Solution {
private:string _s;int n;long mod = 1e9 + 7;// vector<unsigned long long> dp;
public:int numDecodings(string s) {_s = s;n = s.size();// dp.resize(n + 1, -1);// dp[n] = 1;unsigned long long next = 1;unsigned long long nextnext = 0;unsigned long long cur;for (int i = n - 1; i >= 0; i--) {if (_s[i] != '0') {if (_s[i] == '*') {// dp[i] = (unsigned long long)9 * dp[i + 1];cur = (unsigned long long)9 * next;} else {// dp[i] = dp[i + 1];cur = next;}if (i + 1 < n) {if (_s[i] != '*') {if (_s[i + 1] != '*') {if ((_s[i] - '0') * 10 + (_s[i + 1] - '0') <= 26) {// dp[i] += dp[i + 2];cur += nextnext;}} else {if (_s[i] == '1') {// dp[i] += (unsigned long long)9 * dp[i + 2];cur += (unsigned long long)9 * nextnext;}if (_s[i] == '2') {// dp[i] += (unsigned long long)6 * dp[i + 2];cur += (unsigned long long)6 * nextnext;}}} else {if (_s[i + 1] != '*') {if (_s[i + 1] <= '6') {// dp[i] += (unsigned long long)2 * dp[i + 2];cur += (unsigned long long)2 * nextnext;} else {// dp[i] += dp[i + 2];cur += nextnext;}} else {// dp[i] += (unsigned long long)15 * dp[i + 2];cur += (unsigned long long)15 * nextnext;}}}cur = cur % mod;}nextnext = next;next = cur;cur = 0;}return (int)next;}
};