递推与动态规划

======================= **基础知识** =======================

1.递推基础知识：

　　斐波那契(Fibonacii)数列的递推公式：F(n)  = F(n -1) + F(n - 2);

　　70. 爬楼梯: Fibonacci 的最直接体现;

　　前置知识： 数学归纳法：

　　　　a: 验证k₀ 成立；  （边界条件）

　　　　b: 证明如果k_i 成立，那么K_i+1 也成立；（推导公式）

　　　　c: 联合a & b, 证明k₀ -> k_n 成立；

2. 递推问题的步骤：（确定递推公式时候，不要管前一个结果如何得到）

　　1. 确定递推状态（状态方程，学习重点）： 一个函数符号f(x), 以及函数符号的含义描述； 确定自变量x（影响结果的因素有哪些）, 因变量y;

　　2. 确定递推公式（k_i -> k_i+1) ，取决于递推状态的定义；（这里k_i 是第i组对应的满足题意的结果，不要纠结与它怎么得到的！）

　　3. 分析边界条件；

　　4. 程序实现： 递归 或者 循环

　　例子：下面例子中介绍的前两种思路 是更通用的递推思路；

 　　

　　　　比较直接的状态定义：

　　进一步优化状态定义： 

1. 状态的定义： f(n, j) : 第一块涂第0种颜色（这里变成隐变量），最后一块涂第 j 种颜色个数，
 然后乘上颜色个数既可；因为第一块涂的不同颜色对应可能个数是一样的；
2. 那么递推公式： f(n, j) = ∑ f(n -1, k)  |  k != j; 
3.初值条件： f(1, 0) = 1, f(1, 1) = 0, f(1, 2) = 0；
    下面都可由递推公式得到：
     f(2, 0) = f(1, 1) + f(1, 2) = 0, f(2, 1) = f(1, 0) + f(1, 2) = 1, f(2, 2) = f(1, 1) + f(1, 0) = 1;
    f(3, 0) = 0(f(n,0)永远为0), f(3, 1) = f(2, 0) + f(2, 2) = 1, f(3, 2) = f(2, 0) + f(3,1) = 1;
4.最终答案（第一块颜色有3 种可能）：3 * ( f(n - 1, 1) + f(n - 1, 2) ); 

整个过程细节

　　进一步对于题意进行分析：

与题目本身的联系比较紧，普世性差点：

1. 状态定义：f(n) :  n 块环形墙壁时，满足条件个数；
2. 递推公式：第一块 与 第 n - 1 块的颜色不一样情况 
                  第一块 与 第 n - 1块颜色一样，等价与 n - 2 的情况；
3. 初值条件： f(2) = 6, f(3) = 6; //注意f(2)=f(3),必须为初值，因为前后颜色都确定了；
4.最终答案：  f(n) = f(n - 1) + f(n - 2) * 2;

进一步简化（基于具体题目）

3. 递推 与 动态规划 之间的关系：

　a. 动态规划是一种求最优化递推问题，动态规划中涉及到决策过程； 所以动态规划是递推问题的子问题；

　　其中 递推公式 在动态规划中叫做 状态转移方程， 具体步骤与上面递推是类似的；

　b. 在状态转移方程中，主要下面三个重点：

　　　状态定义：

　　　决策过程：从所有可能中选择最优解；　　//如果不涉及决策，大概率就是贪心算法；

　　　阶段依赖：当前阶段只依赖上一阶段； 对于不同问题中，阶段概念是一个很宽泛的定义；

　c. 在实际求解问题过程中，有两种方向：处理问题中，如果从哪里来的条件判断比较复杂，那就可以考虑到哪里去的方法；

　　　　　从哪里来：当前状态 = f(前一个状态 ) ； 　　　　　　　　　　　     　　当前这个状态(被推导) 可以通过其他状态推导得到；

　　　　　到哪里去：每更新当前状态时 ==> 主动更新可以从它推导出状态的结果； 当前这个状态(去推导)可以到达哪些状态；

　　　 这两种方向，本质是一样的，底层是一个图的结构， 而递推(动归) 求解顺序就是状态依赖图的一个拓扑序，对有向图的一维化序列化的结果；

 　d. 动归典型题： 体会从哪里来，到哪里去的精髓；

　　120. 三角形最小路径和 ： 同样的符号，不同的状态定义，递推公式就不一样；决策过程也明确； 当前阶段 与 下一阶段 区分与依赖关系也很明确；

 1 class Solution {
 2 public:
 3     int minimumTotal(vectorint>>& triangle) {
 4 //从上往下，到哪里去
 5         int size = triangle.size();
 6         vectorint>> nums(size, vector<int>(size, INT_MAX));
 7         nums[0][0] = triangle[0][0];
 8 
 9         for(int i = 0, I = size - 1; i < I; ++i) {
10             for(int j = 0; j <= i; ++j){
11                 nums[i + 1][j] = min(nums[i][j] + triangle[i + 1][j], nums[i + 1][j]);
12                 nums[i + 1][j + 1] = min(nums[i][j] + triangle[i + 1][j + 1], nums[i + 1][j + 1]);
13             }
14         }
15 
16         int ans = INT_MAX;
17         for(auto &x : nums[size -1]) ans = min(ans, x);
18         return ans;
19 
20 
21 //rev1: 从下往上， 从哪里来
22 //rev1        int size = triangle.size();
23 //rev1        vector> nums(2, vector(size, 0));
24 //rev1
25 //rev1        int ind = (size - 1) % 2, pre_ind = 0;
26 //rev1        for(int i = 0; i < size; ++i) nums[ind][i] = triangle[size - 1][i];
27 //rev1
28 //rev1        for(int i = size - 2; i >= 0; --i) {
29 //rev1            ind = i % 2;
30 //rev1            pre_ind = !ind;
31 //rev1            for(int j = 0; j <= i; ++j)  
32 //rev1                nums[ind][j] = min(nums[pre_ind][j], nums[pre_ind][j + 1]) + triangle[i][j];
33 //rev1
34 //rev1        }
35 //rev1
36 //rev1        return  nums[0][0];
37     }
38 };

动归典型题

 　e. 动归程序实现中优化； 滚动数组 ==>再压缩，可以顺着/倒着刷表； 记忆化数组；

　　132. 分割回文串 II ：记忆化数组

 1 class Solution {
 2 public:
 3 #define MAX_N 2006
 4     bool mark[MAX_N][MAX_N];
 5 
 6     bool isPalindrome(int l, int r, string s) {
 7         if(s[l] == s[r]) {
 8             if(r - l > 1) mark[l][r] = mark[l + 1][r - 1];
 9             else mark[l][r] = true;
10         }
11         return mark[l][r];
12     }
13 
14     int minCut(string s) {
15         memset(mark, 0, sizeof(mark));
16         int n = s.size();
17         vector<int>dp(n + 1, n); //i 个字符可组成的最少回文个数
18         dp[0] = 0;
19 
20         for(int i = 0, pre = 0; i < n; ++i) {
21             dp[i + 1] = dp[i] + 1;
22             for(int j = pre; j <= i; ++j) {
23                 if(isPalindrome(j, i, s) && dp[j] + 1 < dp[i + 1]) {
24                     dp[i + 1] = dp[j] + 1;
25                     pre = j;
26                 }
27                 pre = max(0, pre - 1);
28             }
29 
30         }
31         return dp[s.size()] - 1;
32     }
33 };

记忆化数组

======================= **代码演示** =======================

 1. 动态规划：  746. 使用最小花费爬楼梯

 1 class Solution {
 2 public:
 3     int minCostClimbingStairs(vector<int>& cost) {
 4 //        int len = cost.size();
 5 //        vector dp(len + 1, 0); 
 6 //        dp[0] = cost[0], dp[1] = cost[1];
 7 //        cost.push_back(0);
 8 //
 9 //        for(int i = 2; i <= len; ++i) {
10 //            dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i];
11 //        }
12 
13         //优化空间使用
14         int dp[3] = {cost[0], cost[1], 0};
15         cost.push_back(0);
16         for(int i = 2, I = cost.size(); i < I; ++i) {
17             int cur = i % 3, pre1 = (i + 3 - 1) % 3, pre2 = (i + 3 - 2) % 3;
18             dp[cur] = min(dp[pre1], dp[pre2]) + cost[i];
19         }
20         return dp[(cost.size() - 1) % 3];
21     }
22 };

动规带有决策的递推

2. 二维动态规划： 1143. 最长公共子序列

 1 class Solution {
 2 public:
 3     int longestCommonSubsequence(string text1, string text2) {
 4         int len1 = text1.size(), len2 = text2.size();
 5         vectorint>> dp(len1 + 1, vector<int>(len2 + 1, 0));
 6 
 7         for(int i = 1; i <= len1; i++) {
 8             for(int j = 1; j <= len2; j++) {
 9                 dp[i][j] = max(dp[i - 1][j - 1] + (text1[i - 1] == text2[j - 1]),
10                             max(dp[i][j - 1], dp[i - 1][j]));
11             }
12         }
13         return dp[len1][len2];
14     }
15 };
16 //状态方程： dp[i][j] 代表text1 长度为i, text2长度为j 的最长公共子序列长度；i 不一定要等于 j
17 //状态转移方程：
18 //      dp[i][j] = max(dp[i][j - 1], 
19 //                     dp[i -1][j],
20 //                     dp[i - 1][j - 1] + (text1[i] == text2[j]));  //这一组只有在text1[i] == text2[j] 才有必要
21 //

二维动归典型题

 ======================= **经典问题** =======================

1. 相邻互斥，动态过程最优解；

 　　剑指 Offer II 091. 粉刷房子

 1 class Solution {
 2 public:
 3     int minCost(vectorint>>& costs) {
 4         vectorint>> dp(2, costs[0]);
 5 
 6         for(int i = 1, I = costs.size(); i < I; ++i) {
 7             int cur = i % 2, pre = !cur;
 8             dp[cur][0] = min(dp[pre][1], dp[pre][2]) + costs[i][0];
 9             dp[cur][1] = min(dp[pre][0], dp[pre][2]) + costs[i][1];
10             dp[cur][2] = min(dp[pre][0], dp[pre][1]) + costs[i][2];
11         }
12 
13         int idx = (costs.size() - 1) % 2;
14         return min(dp[idx][0], min(dp[idx][1], dp[idx][2]));
15     }
16 };

动归/滚动数组

 　　198. 打家劫舍

 1 class Solution {
 2 public:
 3     int rob(vector<int>& nums) {
 4         int len = nums.size();
 5         vectorint>> dp(2, vector<int>(2)); //偷/不偷 对应的最大值
 6         dp[0][0] = nums[0];
 7         for(int i = 1; i < len; ++i) {
 8             int cur = i % 2, pre = !cur;
 9             dp[cur][0] = nums[i] + dp[pre][1];
10             dp[cur][1] = max(dp[pre][0], dp[pre][1]);
11         }
12         len -= 1;
13         return max(dp[len % 2][0], dp[len % 2][1]);
14     }
15 };

动归

　　213. 打家劫舍 II

 1 class Solution {
 2 public:
 3     int rob(vector<int>& nums) {
 4         int n = nums.size();
 5         if(n == 1) return nums[0];
 6 
 7         int dp1[2][2] = {nums[0]}, dp2[2][2] = {0};
 8 
 9         //第一家一定偷
10         dp1[0][0] = dp1[0][1] = dp1[1][0] = dp1[1][1] = nums[0];
11         for(int i = 2; i < n; ++i) {
12             int idx = i % 2, pre = !idx;
13             dp1[idx][0] = dp1[pre][1] + nums[i];   //偷；
14             dp1[idx][1] = max(dp1[pre][0], dp1[pre][1]); //不偷;
15         }
16         //第一家一定不偷
17         for(int i = 1; i < n; ++i) {
18             int idx = i % 2, pre = !idx;
19             dp2[idx][0] = dp2[pre][1] + nums[i]; //偷
20             dp2[idx][1] = max(dp2[pre][0], dp2[pre][1]); //不偷
21         }
22 
23         n--;
24         return max(dp1[n % 2][1], max(dp2[n % 2][0], dp2[n % 2][1]));
25     }
26 };
27 
28 //original
29 //
30 class Solution {
31 public:
32     int rob(vector<int>& nums) {
33 //rev2: 存储空间优化方案
34         int size = nums.size();
35         if(size == 1) return nums[0];
36        vectorint>> rob(2, vector<int>(2, 0));
37        int ret = 0;
38     //最后一家一定不抢
39         rob[0][0] = 0;
40         rob[0][1] = nums[0];
41        for(int i = 1, I = size - 1; i < I; ++i) {
42            int ind = i % 2, pre_ind = !ind;
43            rob[ind][0] = max(rob[pre_ind][0], rob[pre_ind][1]);
44            rob[ind][1] = rob[pre_ind][0] + nums[i];
45        }
46        int last_ind = (size - 2) % 2;
47        ret = max(rob[last_ind][0], rob[last_ind][1]);
48 
49     //第一家一定不抢
50         rob[0][0] = rob[0][1] = rob[1][0] = rob[1][1] = 0;
51         for(int i = 1; i < size; ++i) {
52             int ind = i % 2, pre_ind = !ind;
53             rob[ind][0] = max(rob[pre_ind][0], rob[pre_ind][1]);
54             rob[ind][1] = rob[pre_ind][0] + nums[i];
55         }
56         last_ind = (size - 1) % 2;
57         ret = max(ret, max(rob[last_ind][0], rob[last_ind][1]));
58 
59 //rev1: 无任何优化方式
60 //        int size = nums.size();
61 //        if(size == 1) return nums[0];
62 //        vector> rob(size, vector(2, 0));
63 //        int ret = 0;
64 //// 第一家随意，最后一家一定不抢
65 //        rob[0][0] = 0;
66 //        rob[0][1] = nums[0];
67 //        for(int i = 1, I = size - 1; i < I; ++i) {
68 //            rob[i][0] = max(rob[i - 1][0], rob[i -1][1]);
69 //            rob[i][1] = rob[i -1][0] + nums[i];
70 //        }
71 //        ret = max(rob[size -2][0], rob[size -2][1]); 
72 ////第一家不抢， 最后一家随意
73 //        rob[0][1] = 0; 
74 //        for(int i = 1; i < size; ++i) {
75 //            rob[i][0] = rob[i][1] = 0;
76 //            rob[i][0] = max(rob[i - 1][0], rob[i - 1][1]);
77 //            rob[i][1] = rob[i -1][0] + nums[i];
78 //        }
79 //
80 //        ret = max(ret, max(rob[size -1][0], rob[size -1][1]));
81         return ret;
82     }
83 };

状态定义/转移

 　　152. 乘积最大子数组

 1 class Solution {
 2 public:
 3     int maxProduct(vector<int>& nums) {
 4         int ans = INT_MIN, max_val = 1, min_val = 1;
 5 
 6         for(auto &x : nums) {
 7             if(x < 0) swap(max_val, min_val);
 8             max_val = max(max_val * x, x);
 9             min_val = min(min_val * x, x);
10             ans = max(ans, max_val);
11         }
12         return ans;
13     }
14 };
15 
16 //f(n) 以当前位置结尾的最大/最小值

状态定义

2.最长上升子序列：

 　　300. 最长递增子序列

 1 class Solution {
 2 public:
 3     int bs_01(vector<int>& arr, int num) {
 4         int l = 0, r = arr.size(), mid;
 5         while(l < r) {
 6             mid = (l + r) >> 1;
 7             if(arr[mid] < num) l = mid + 1;
 8             else r = mid;
 9         }
10         return l;
11     }
12 
13     int lengthOfLIS(vector<int>& nums) {
14 //优化解法
15         vector<int> arr;
16         for(auto &x : nums) {
17             if(arr.empty() || arr.back() < x) arr.push_back(x);
18             else arr[bs_01(arr, x)] = x;
19         }
20         return arr.size();
21 
22 //基础解法dp
23 //        vector dp(nums.size(), 0);
24 //        map m;
25 //        int ans = 0;
26 //        for(int i = 0, I = nums.size(); i < I; ++i) {
27 //            m[nums[i]] = i;
28 //            auto it = m.find(nums[i]);
29 //            while(it != m.begin()) dp[i] = max(dp[i], dp[(--it)->second]);
30 //            dp[i] += 1;
31 //            ans = max(ans, dp[i]);
32 //        }
33 //        return ans;
34 //dp(n) 以n 为结尾的子数组长度；
35     }
36 };

状态定义/优化

　　714. 买卖股票的最佳时机含手续费

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices, int fee) {
 4         int n = prices.size();
 5         vectorint>> dp(2, vector<int>(2, 0));  //第i 天 持有/不持有
 6         dp[0][0] = -prices[0], dp[0][1] = 0;
 7         for(int i = 1; i < n; ++i) {
 8             int idx = i % 2, pre = !idx;
 9             dp[idx][0] =  max(dp[pre][0], dp[pre][1] - prices[i]);//持有
10             dp[idx][1] =  max(dp[pre][0] + prices[i] - fee, dp[pre][1]);//不持有
11         }
12 
13         return dp[!(n % 2)][1];
14     }
15 };

动归

3. 典型的0/1 背包问题； 资源有限的情况下收益最大化问题； 对于当前值，就两种可能，要么选，要么不选;

　　416. 分割等和子集 ：可达数组类型， 倒着刷表

 1 class Solution {
 2 public:
 3 
 4     bool canPartition(vector<int>& nums) {
 5         int total = 0;
 6         for(auto &x : nums) total += x;
 7         if(total % 2) return false;
 8         total /= 2;
 9 
10         //dp[i][j] : 前i个数字，能否凑出j值；
11         //dp[i][j] : dp[i - 1][j] | dp[i - 1][j - nums[i]
12         //优化：当前i状态 只与前面所有可能到达状态相关, 
13         //      从后往前，保证当前i状态 由 所有前面的状态决定
14         vector<bool> dp(total + 1, false); 
15         dp[0] = true;
16 
17         for(auto &x : nums){
18             for(int i = total - x; i >= 0; --i) {
19                 if(dp[i]) dp[i + x] = true;
20             }
21             if(dp[total]) return true;
22         }
23         return false;
24     }
25 };

优化

 　　474. 一和零

 1 class Solution {
 2 public:
 3     int findMaxForm(vector<string>& strs, int m, int n) {
 4         //dp[i][m][n] : 第i 个str, 取m 个 0， n 个 1 的最多子集树；
 5         //dp[i][m][n] = max(dp[i - 1][m][n] , dp[i - 1][n - cnt0][n - cnt1]) //选 ， 不选对应可能
 6         //优化：当前i 结果只与 前面所有可能状态相关； 注意方向，保证是取 i 前面可能状态；
 7         
 8         vectorint>> dp(m + 1, vector<int>(n + 1, 0));  //i 个0， j 个1 的有可能取到最多子集数；
 9 
10         for(int i = 0, I = strs.size(); i < I; ++i) {
11             int idx = 0, cnt0 = 0, cnt1 = 0;
12             while(strs[i][idx]) cnt0 += (strs[i][idx++] == '0');
13             cnt1 = strs[i].size() - cnt0;
14 
15             for(int x = m; x >= cnt0; --x) {
16                 for(int y = n; y >= cnt1; --y) {
17                     dp[x][y] = max(dp[x][y], dp[x - cnt0][y - cnt1] + 1);
18                 }
19             }
20         }
21         return dp[m][n];
22     }
23 };

优化

 　　494. 目标和 // 到哪里去

 1 class Solution {
 2 public:
 3     int findTargetSumWays(vector<int>& nums, int target) {
 4 //Rev2: 滚动数组/可达数组/偏移量
 5         int sum = 0;
 6         for(auto &x : nums) sum += x;
 7         if(target > sum || target < -sum) return 0;
 8         //偏移量，滚动数组
 9         int buff[2][2 * sum + 5], *f[2] = {buff[0] + sum + 2, buff[1] + sum + 2};
10         memset(buff, 0, sizeof(buff));
11         f[1][0] = 1;
12         sum = 0;
13 
14         for(int i = 0, I = nums.size(); i < I; ++i) {
15             int cur = i % 2, pre = !cur;
16             memset(buff[cur], 0, sizeof(buff[cur]));
17             for(int j = -sum; j <= sum; ++j) {
18                 f[cur][j + nums[i]] += f[pre][j];
19                 f[cur][j - nums[i]] += f[pre][j];
20             }
21             sum += nums[i];
22         }
23 
24         int idx = !(nums.size() % 2);
25         return f[idx][target];
26         
27 //Rev1: 滚动数组/可达数组
28 //        vector> dp(2);
29 //        //i位置可以组成的和为nums的个数
30 //        dp[0][nums[0]] += 1, dp[0][-nums[0]] += 1;
31 //        for(int i = 1, I = nums.size(); i < I; ++i) {
32 //            int idx = i % 2, pre = !idx;
33 //            dp[idx].clear();
34 //            for(auto &x : dp[pre]) {
35 //                //我到哪里去
36 //                dp[idx][x.first + nums[i]] += x.second;
37 //                dp[idx][x.first - nums[i]] += x.second;
38 //            }
39 //        }
40 //
41 //        int idx = !(nums.size() % 2);
42 //        return dp[idx][target];
43     }
44 };

滚动数组/偏移量

4. 凑硬币类型：

　　322. 零钱兑换： 正着刷表 　　

 1 class Solution {
 2 public:
 3     int coinChange(vector<int>& coins, int amount) {
 4 //优化版本
 5         vector<int> dp(amount + 5, -1); //总数为i时候，需要的硬币总数
 6         dp[0] = 0;  
 7         for(auto &x : coins) { //使用前n 种硬币可以组成的各个金额总数
 8             for(int i = x; i <= amount; ++i) {
 9                 if(-1 == dp[i - x]) continue;
10                 if(-1 == dp[i] || dp[i] > dp[i - x] + 1) dp[i] = dp[i - x] + 1;
11             }
12         }
13         return dp[amount];
14 
15 //初始版本, 而且下面两个循环之间互换，有些情况下影响很大，例如518题
16 //        sort(coins.begin(), coins.end());
17 //        vector nums;
18 //        for(auto &x : coins){   //减枝过程,可优化
19 //            if(x > amount) break;
20 //            nums.push_back(x);
21 //        }
22 //
23 //        for(int i = 0; i <= amount; i++) {
24 //            if(dp[i] == -1) continue;
25 //            for(auto &x : nums) {
26 //                int val = x + i;
27 //                if(val > amount) break;  
28 //                if(dp[val] == -1) dp[val] = dp[i] + 1; //可优化
29 //                else dp[val] = min(dp[val], dp[i] + 1);
30 //            }
31 //        }
32 //        return dp[amount];
33     }
34 };

正着刷表

　　518. 零钱兑换 II ： 递推/正向刷表；

 1 class Solution {
 2 public:
 3     int change(int amount, vector<int>& coins) {
 4         //dp[i][j] = dp[i - 1][j] + dp[i][j - x], 可优化成下面正向刷表;
 5         vector<int> dp(amount + 1, 0);  //i 金额对应的硬币组合个数
 6         dp[0] = 1;  
 7 
 8         for(auto &x : coins) { //使用前 x种硬币时候，各个金额可能的组合
 9             for(int i = x; i <= amount; ++i) {
10                 dp[i] += dp[i - x];
11             }
12         }
13         return dp[amount];
14     }
15 };

递推/正向刷表

 　　377. 组合总和 Ⅳ : 这题与322， 518 三题综合起来看，包含了最佳，不计顺序，计算顺序的不同要求对应的不同操作；

 1 class Solution {
 2 public:
 3     int combinationSum4(vector<int>& nums, int target) {
 4         vectorint> dp(target + 1, 0);
 5         sort(nums.begin(), nums.end());
 6 
 7         dp[0] = 1;
 8         //到哪里去
 9         for(int i = 0; i <= target; ++i) {  //当前金额可以实现哪些新的金额
10             if(!dp[i]) continue;
11             for(auto &x : nums) {
12                 int val = i + x;
13                 if(val > target) break;
14                 dp[val] += dp[i];
15             }
16         }
17         return dp[target];
18     }
19 };
20 
21 //original
22 class Solution {
23 public:
24     int combinationSum4(vector<int>& nums, int target) {
25         vectorint> cnt(target + 1, 0);
26         cnt[0] = 1; 
27         sort(nums.begin(), nums.end());
28         //从哪里来
29         for(int i = 1; i <= target; ++i) {  //当前金额，可以由哪些金额组成
30             for(auto &x : nums) {
31                 if(x > i) break; 
32                 cnt[i] += cnt[i - x];
33             }
34         }
35 
36         return cnt[target];
37     }
38 };

从哪里来/到哪里去

 
======================= **应用场景** =======================