动态规划：用空间代替重复计算，包含一整套原理和技巧的总和。后面会有非常多的文章介绍动态规划。
有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益。如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要。任何动态规划问题都一定对应着一个有重复调用行为的递归。所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法。尝试策略就是转移方程，完全一回事。推荐从尝试入手，因为代码好写，并且一旦发现尝试错误，重新想别的递归代价轻。
当熟悉了从递归到动态规划的转化过程，那么就可以纯粹用动态规划的视角来分析问题了。如果不熟悉这个过程，直接一上来就硬去理解状态转移方程，那么往往会步履维艰、邯郸学步、东施效颦。
动态规划的大致过程：想出设计优良的递归尝试(方法、经验、固定套路很多)，有关尝试展开顺序的说明
-> 记忆化搜索(从顶到底的动态规划) ，如果每个状态的计算枚举代价很低，往往到这里就可以了。
-> 严格位置依赖的动态规划(从底到顶的动态规划) ，更多是为了下面说的进一步优化枚举做的准备。
-> 进一步优化空间（空间压缩），一维、二维、多维动态规划都存在这种优化。
-> 进一步优化枚举也就是优化时间（本文没有涉及，但是后续巨多内容和这有关）。
解决一个问题，可能有很多尝试方法，众多的尝试方法中，可能若干的尝试方法有重复调用的情况，可以转化成动态规划。若干个可以转化成动态规划的方法中，又可能有优劣之分。判定哪个是最优的动态规划方法，依据来自题目具体参数的数据量。最优的动态规划方法实现后，后续又有一整套的优化技巧。
下面通过一些题目入手动态规划。
题目一
测试链接：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;
}
};其中，因为数目过大采用同余原理处理结果。