算法【从递归入手一维动态规划】

动态规划：用空间代替重复计算，包含一整套原理和技巧的总和。后面会有非常多的文章介绍动态规划。

有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益。如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要。任何动态规划问题都一定对应着一个有重复调用行为的递归。所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法。尝试策略就是转移方程，完全一回事。推荐从尝试入手，因为代码好写，并且一旦发现尝试错误，重新想别的递归代价轻。

当熟悉了从递归到动态规划的转化过程，那么就可以纯粹用动态规划的视角来分析问题了。如果不熟悉这个过程，直接一上来就硬去理解状态转移方程，那么往往会步履维艰、邯郸学步、东施效颦。

动态规划的大致过程：想出设计优良的递归尝试(方法、经验、固定套路很多)，有关尝试展开顺序的说明

-> 记忆化搜索(从顶到底的动态规划) ，如果每个状态的计算枚举代价很低，往往到这里就可以了。

-> 严格位置依赖的动态规划(从底到顶的动态规划) ，更多是为了下面说的进一步优化枚举做的准备。

-> 进一步优化空间（空间压缩），一维、二维、多维动态规划都存在这种优化。

-> 进一步优化枚举也就是优化时间（本文没有涉及，但是后续巨多内容和这有关）。

解决一个问题，可能有很多尝试方法，众多的尝试方法中，可能若干的尝试方法有重复调用的情况，可以转化成动态规划。若干个可以转化成动态规划的方法中，又可能有优劣之分。判定哪个是最优的动态规划方法，依据来自题目具体参数的数据量。最优的动态规划方法实现后，后续又有一整套的优化技巧。

下面通过一些题目入手动态规划。

题目一

测试链接：https://leetcode.cn/problems/fibonacci-number/

分析：斐波那契数是一个极其经典的动态规划问题。我们借由这个题目展开对动态规划的讨论，首先，我们使用一个递归暴力解法。代码如下。

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

其中，因为题目的数据量不大，所以递归暴力解法也能通过。下面使用记忆化搜索的解法，就是用一个数组把计算过的结果存储起来，以后要计算相同结果的时候直接使用。代码如下。

class Solution {
public:vector<int> record;int f(int n){if(n == 0){return 0;}if(n == 1){return 1;}if(record[n] != -1){return record[n];}int ans = f(n-1) + f(n-2);record[n] = ans;return ans;}int fib(int n) {record.assign(n+1, -1);return f(n);}
};

其中，对于f(n)，如果record[n]不等于-1也就是计算过了，直接返回；如果等于-1，也就是并未计算出结果，就直接计算，然后将结果存入数组。记忆化搜索的解法已经很快了，接下来，我们看看严格位置依赖的解法，也就是普遍的动态规划。可以看出，f(n)的结果是依赖于f(n-1)和f(n-2)，所以我们从前向后遍历dp数组，计算逻辑和递归以及记忆化搜索一样。代码如下。

class Solution {
public:vector<int> dp;int f(int n){if(n == 0){return 0;}if(n == 1){return 1;}dp[0] = 0;dp[1] = 1;for(int i = 2;i <= n;++i){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}int fib(int n) {dp.assign(n+1, 0);return f(n);}
};

其中，将dp数组初始化后开始遍历dp数组计算结果。有了严格位置依赖的解法，我们可以从空间上去优化，也就是空间压缩。可以看出，dp[i]只依赖于dp[i-1]和dp[i-2]，所以我们只需要用3个变量表示即可。代码如下。

class Solution {
public:int cur, last, lastLast;int f(int n){if(n == 0){return 0;}if(n == 1){return 1;}lastLast = 0;last = 1;for(int i = 2;i <= n;++i){cur = last + lastLast;lastLast = last;last = cur;}return cur;}int fib(int n) {return f(n);}
};

其中，cur表示dp[i]，last表示dp[i-1]，lastLast表示dp[i-2]。

题目二

测试链接：https://leetcode.cn/problems/minimum-cost-for-tickets/

分析：这个问题我们依然从递归解法开始，一步步推广到动态规划。f方法表示的意思是从下标为i的天数开始所需要的最小花费。因为纯递归暴力解法会超时，所以直接从记忆化搜索解法展示。代码如下。

class Solution {
public:vector<int> dp;int plan[3] = {1, 7, 30};int f(int i, vector<int>& days, vector<int>& costs){if(i >= days.size()){return 0;}if(dp[i] != -1){return dp[i];}int cur = days[i];int ans = -((1 << 31) + 1);int day, j;for(int p = 0;p < 3;++p){j = i + 1;day = plan[p];while (j < days.size() && cur + day > days[j]){++j;}ans = ans < costs[p]+f(j, days, costs) ? ans : costs[p]+f(j, days, costs);}dp[i] = ans;return ans;}int mincostTickets(vector<int>& days, vector<int>& costs) {dp.assign(366, -1);return f(0, days, costs);}
};

其中，递归主题思路是在当前天分别购买1、7、30天，然后从下一次需要购买的下标继续递归调用。记忆化搜索的解法只是比递归解法多了一个数组来存储结果，下面我们来看严格位置依赖的解法。可以看出，小下标依赖大下标的结果，所以从后向前遍历dp数组。代码如下。

class Solution {
public:int dp[366];int plan[3] = {1, 7, 30};int mincostTickets(vector<int>& days, vector<int>& costs) {int length = days.size();int cur, day, k;dp[length-1] = costs[0] < costs[1] ? (costs[0] < costs[2] ? costs[0] : costs[2]) : (costs[1] < costs[2] ? costs[1] : costs[2]);for(int i = length-2;i >= 0;--i){cur = days[i];dp[i] = costs[0] + dp[i+1];for(int j = 1;j < 3;++j){day = plan[j];k = i + 1;while (k < length && cur + day > days[k]){++k;}if(k == length){dp[i] = dp[i] < costs[j] ? dp[i] : costs[j];}else{dp[i] = dp[i] < costs[j]+dp[k] ? dp[i] : costs[j]+dp[k];}}}return dp[0];}
};

其中，计算逻辑和记忆化搜索相同。

题目三

测试链接：https://leetcode.cn/problems/decode-ways/

分析：这道题我们也先从记忆化搜索，也就是先从递归考虑尝试，然后再推广到严格位置依赖的解法。f方法表示，从下标i向后有多少种解码方法。代码如下。

class Solution {
public:vector<int> dp;int f(string s, int i){int ans;if(i >= s.size()){return 1;}if(dp[i] != -1){return dp[i];}if(s[i] == '0'){return 0;}ans = f(s, i+1);if(i+1 < s.size()&& ((s[i] == '1') || (s[i] == '2' && s[i+1] >= '0' && s[i+1] <= '6'))){ans += f(s, i+2);}dp[i] = ans;return ans;}int numDecodings(string s) {dp.assign(101, -1);return f(s, 0);}
};

其中，如果s[i]等于0则没有解码方法，如果有，先将s[i]单独划分成一个，然后再判断是否能讲s[i]和s[i+1]划分成一个。对于严格位置依赖的解法，我们可以看出小下标的结果依赖于大下标的结果，所以也是从后向前遍历dp数组，计算逻辑和记忆化搜索相同。代码如下。

class Solution {
public:int dp[101];int numDecodings(string s) {int length = s.size();dp[length] = 1;for(int i = length-1;i >= 0;--i){if(s[i] == '0'){dp[i] = 0;}else{dp[i] = dp[i+1];if(i+1 < length&& ((s[i] == '1') || (s[i] == '2' && s[i+1] >= '0' && s[i+1] <= '6'))){dp[i] += dp[i+2];}}}return dp[0];}
};

其中，计算完dp数组后dp[0]就是结果。再来从空间上压缩一下，这以看出i位置的结果依赖于i+1和i+2的结果，所以同样可以用三个变量来表示。代码如下。

class Solution {
public:int cur, next, nextNext;int numDecodings(string s) {int length = s.size();next = 1;for(int i = length-1;i >= 0;--i){if(s[i] == '0'){cur = 0;}else{cur = next;if(i+1 < length&& ((s[i] == '1') || (s[i] == '2' && s[i+1] >= '0' && s[i+1] <= '6'))){cur += nextNext;}}nextNext = next;next = cur;}return cur;}
};​

其中，cur表示dp[i]，next表示dp[i+1]，nextNext表示dp[i+2]。

题目四

测试链接：https://leetcode.cn/problems/decode-ways-ii/

分析：这道题和上道题思路差不多，只不过讨论的情况更多。同时，这道题如果使用记忆化搜索，会导致爆栈，所以只展示严格位置依赖的解法和空间压缩的解法。代码如下。

class Solution
{
public:int MOD = 1000000007;int dp[100002];int numDecodings(string s){int length = s.size();dp[length] = 1;for (int i = length - 1; i >= 0; --i){if (s[i] == '0'){dp[i] = 0;}else{if (s[i] > '0' && s[i] <= '9'){dp[i] = dp[i+1];}else{dp[i] = (9 * (long long)dp[i+1]) % MOD;}if (i + 1 < length){if (s[i] == '1' && s[i + 1] >= '0' && s[i + 1] <= '9'){dp[i] = (dp[i] + dp[i+2]) % MOD;}else if (s[i] == '2' && s[i + 1] >= '0' && s[i + 1] <= '6'){dp[i] = (dp[i] + dp[i+2]) % MOD;}else if (s[i] == '1' && s[i + 1] == '*'){dp[i] = (dp[i] + (9 * (long long)dp[i+2])) % MOD;}else if (s[i] == '2' && s[i + 1] == '*'){dp[i] = (dp[i] + (6 * (long long)dp[i+2])) % MOD;}else if (s[i] == '*' && s[i + 1] >= '0' && s[i + 1] <= '6'){dp[i] = (dp[i] + (2 * (long long)dp[i+2])) % MOD;}else if (s[i] == '*' && s[i + 1] > '6' && s[i + 1] <= '9'){dp[i] = (dp[i] + dp[i+2]) % MOD;}else if (s[i] == '*' && s[i + 1] == '*'){dp[i] = (dp[i] + (15 * (long long)dp[i+2])) % MOD;}}}}return dp[0];}
};

其中，和上道题一样，对于所有情况进行讨论，这里不再赘述。下面展示空间压缩的解法。代码如下。

class Solution
{
public:int MOD = 1000000007;int cur, next, nextNext;int numDecodings(string s){int length = s.size();next = 1;for (int i = length - 1; i >= 0; --i){if (s[i] == '0'){cur = 0;}else{if (s[i] > '0' && s[i] <= '9'){cur = next;}else{cur = (9 * (long long)next) % MOD;}if (i + 1 < length){if (s[i] == '1' && s[i + 1] >= '0' && s[i + 1] <= '9'){cur = (cur + nextNext) % MOD;}else if (s[i] == '2' && s[i + 1] >= '0' && s[i + 1] <= '6'){cur = (cur + nextNext) % MOD;}else if (s[i] == '1' && s[i + 1] == '*'){cur = (cur + (9 * (long long)nextNext)) % MOD;}else if (s[i] == '2' && s[i + 1] == '*'){cur = (cur + (6 * (long long)nextNext)) % MOD;}else if (s[i] == '*' && s[i + 1] >= '0' && s[i + 1] <= '6'){cur = (cur + (2 * (long long)nextNext)) % MOD;}else if (s[i] == '*' && s[i + 1] > '6' && s[i + 1] <= '9'){cur = (cur + nextNext) % MOD;}else if (s[i] == '*' && s[i + 1] == '*'){cur = (cur + (15 * (long long)nextNext)) % MOD;}}}nextNext = next;next = cur;}return cur;}
};

其中，cur，next，nextNext含义和上一题相同。

题目五

测试链接：https://leetcode.cn/problems/ugly-number-ii/

分析：现在我们就直接给出严格位置依赖的解法，不再对递归以及记忆化搜索的解法进行展示。对于丑数，可以知道1是第一个丑数。所以我们设置2指针，3指针和5指针，初始化指向第一个丑数也就是1。然后要得到后续的丑数时，将2指针指向的丑数乘以2，,3指针指向的丑数乘以3，,5指针指向的丑数乘以5，得到其中最小值就是当前的丑数。然后指针计算的结果小于等于得到丑数的，将指针后移指向下一个丑数。代码如下。

class Solution {
public:int dp[1692];int nthUglyNumber(int n) {if(n == 1){return 1;}int ptr_2 = 1, ptr_3 = 1, ptr_5 = 1, i = 2;dp[1] = 1;while (i <= n){dp[i] = dp[ptr_2] * 2 < dp[ptr_3] * 3 ?(dp[ptr_2] * 2 < dp[ptr_5] * 5 ? dp[ptr_2] * 2 : dp[ptr_5] * 5) :(dp[ptr_3] * 3 < dp[ptr_5] * 5 ? dp[ptr_3] * 3 : dp[ptr_5] * 5);if(dp[ptr_2] * 2 <= dp[i]){++ptr_2;}if(dp[ptr_3] * 3 <= dp[i]){++ptr_3;}if(dp[ptr_5] * 5 <= dp[i]){++ptr_5;}++i;}return dp[n];}
};

其中，通过一个嵌套的三目运算符来得到计算出的最小值。

题目六

测试链接：https://leetcode.cn/problems/longest-valid-parentheses/

分析：dp数组的含义是以下标i为结尾的有效子串最长长度。所以我们可以知道，当s[i]为左括号的时候，结果为dp[i]为0。当s[i]为右括号的时候开始讨论，设p是s[i-1]向左最长长度之后再左一个位置的下标，如果此时s[p]有效且s[p]为左括号则dp[i]=dp[i-1]+2，此时，如果p的左边仍然连接了一个有效的子串，则可以将这个子串的长度加上。遍历数组即可得到答案。代码如下。

class Solution {
public:int dp[30002] = {0};int longestValidParentheses(string s) {int length = s.size();int ans = 0;for(int i = 1, p;i < length;++i){if(s[i] == ')'){p = i - dp[i-1] - 1;if(p >= 0 && s[p] == '('){dp[i] = dp[i-1] + 2 + (p-1 >= 0 ? dp[p-1] : 0);}}ans = ans > dp[i] ? ans : dp[i];}return ans;}
};

其中，三目运算符就是在判断p左边是否还连接了一个有效子串。

题目七

测试链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

分析：对于这个题，我们可以先求得s串中以a到z字母为结尾的最长有序子串长度，这样可以避免重复计算结果，然后将每一个最长长度相加，即是答案。代码如下。

class Solution {
public:int longest[26] = {0};int findSubstringInWraproundString(string s) {int length = s.size();int len = 1;int ans = 0;longest[s[0]-'a'] = 1;for(int i = 1;i < length;++i){if((s[i] - s[i-1] + 26) % 26 == 1){longest[s[i]-'a'] = longest[s[i]-'a'] > ++len ? longest[s[i]-'a'] : len;}else{len = 1;longest[s[i]-'a'] = longest[s[i]-'a'] > 1 ? longest[s[i]-'a'] : 1;}}for(int i = 0;i < 26;++i){ans += longest[i];}return ans;}
};

其中，len就是s中到了下标i对于下标i字母为结尾的有序子串长度。

题目八

测试链接：https://leetcode.cn/problems/distinct-subsequences-ii/

分析：这个计算思路可以积累下来，十分好用。all代表当前集合数，初始化为1，代表1个空集，后面返回结果是减去；cur代表当前遍历到的字符；add代表新增的集合数目；nums数组存储以a到z字母为结尾的子序列数目。主要流程是：遍历到cur字符时，新增的不重复集合数目为all减去当前以cur为结尾的子序列数目，然后更新以cur为结尾的子序列的数目，更新当前集合数目。遍历完字符串即可得到答案。代码如下。

class Solution {
public:int nums[26] = {0};int MOD = 1000000007;int distinctSubseqII(string s) {int all = 1;int length = s.size();char cur;int add;for(int i = 0;i < length;++i){cur = s[i];add = (all - nums[cur-'a'] + MOD) % MOD;nums[cur-'a'] = (nums[cur-'a'] + add) % MOD;all = (all + add) % MOD;}return (all - 1 + MOD) % MOD;}
};

其中，因为数目过大采用同余原理处理结果。