数据结构与算法——从递归入手一维动态规划【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;}
};