动态规划总论:状态设计的要点和技巧
再探:零钱兑换问题
零钱兑换
https://leetcode.cn/problems/coin-change/
给一个硬币面额的可选集合coins，求拼成金额amount最少需要多少枚硬币。
例: coins = [20,10,5,1],amount = 46
答案:46= 20+ 20+5+1
零钱兑换:搜索
状态:剩余金额、已用硬币枚数
零钱兑换:最优子结构
状态中没有必要包含“已用硬币枚数”
对于每个“剩余金额”，搜一次，求出“兑换这个金额所需的最少硬币枚数”就足够了
原始状态:剩余金额、已用硬币枚数，目标:到达终点(O元)
新状态:剩余金额，最优化目标:硬币枚数最少
推导关系:“兑换n元的最少硬币枚数”
opt(n)= min(opt(n - 1), opt(n - 9), opt(n- 10))+1
状态＋最优化目标＋最优化目标之间具有递推关系=最优子结构
零钱兑换:最优子结构
零钱兑换: 递推实现
class Solution { public int coinChange(int[] coins, int amount) { int INF = (int)1e9; int[] opt = new int[amount + 1]; opt[0] = 0; for(int i = 1; i <= amount; i++) { opt[i] = INF; for(int j = 0;j < coins.length; j++){ if(i - coins[j] >= 0) opt[i] = Math.min(opt[i], opt[i - coins[j]] + 1); } } if(opt[amount] >= INF) opt[amount] = -1; return opt[amount]; } }
零钱兑换: 记忆化搜索
class Solution { vector<int>count; int dp(vector<int>& coins, int rem) { if (rem < 0) return -1; if (rem == 0) return 0; if (count[rem - 1] != 0) return count[rem - 1]; int Min = INT_MAX; for (int coin:coins) { int res = dp(coins, rem - coin); if (res >= 0 && res < Min) { Min = res + 1; } } count[rem - 1] = Min == INT_MAX ? -1 : Min; return count[rem - 1]; } public: int coinChange(vector<int>& coins, int amount) { if (amount < 1) return 0; count.resize(amount); return dp(coins, amount); } };
无论是递推实现还是记忆化搜索（递归实现)
这种定义状态＋最优子结构＋推导关系的解题方法
其实就是动态规划算法
简单的线性动态规划
**动态规划(DP, dynamic programming)**是一种对问题的状态空间进行分阶段、有顺序、不重复、决策性遍历的算法
动态规划的关键与前提:
重叠子问题——与递归、分治等一样，要具有同类子问题，用若干维状态表示最优子结构——状态对应着一个最优化目标，并且最优化目标之间具有推导关系无后效性——问题的状态空间是一张有向无环图（可按一定的顺序遍历求解)
动态规划一般采用递推的方式实现
也可以写成递归或搜索的形式，因为每个状态只遍历一次，也被称为记忆化搜索
动态规划三要素:阶段、状态、决策
一道动态规划题目的标准题解:
设opt[i]表示凑成金额 i 所需的最少硬币数
状态转移方程
边界
目标
时间复杂度
一道动态规划题目，写出状态转移方程，就已经完成了大半的工作
剩下的任务就是照着方程写几个循环递推实现就行了
实战
63.不同路径Ⅱ
https://leetcode.cn/problems/unique-paths-ii/
一个机器人位于一个m x n网格的左上角
机器人每次只能向下或者向右移动一步机
器人试图达到网格的右下角
现在考虑网格中有障碍物
那么从左上角到右下角将会有多少条不同的路径?
Bottom-up
f[i,j]表示从(i,j)到End的路径数
如果(i,j)是空地，fli,j]= f[i＋1,j+f Li,j＋1]
否则f[ti,j= 0
Top-down
f[,j]表示从Start到(i,j)的路径数
如果i,j)是空地，f Li,j]= f[i-1,j]+ f li,j-1]
否则ft,j]= 0
Bottom-up记忆化搜索（递归、分治思想)
int countPaths(boolean[][ ]grid，int row，int col) { if ( !validSquare(grid，row,col)) return 0; if (isAtEnd(grid，row，col)) return 1; return countPaths(grid，row + 1，col) + countPaths(grid，row，col + 1); }
1143.最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n=text1.size(); int m=text2.size(); vector<vector<int>> dp(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(text1[i-1]==text2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; }else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } return dp[n][m]; } };
给两个字符串，求最长公共子序列(LCS)，例如:
text1 = “abcde”
text2 = “ace”
入手DP问题第一步:人工模拟的话怎么算?
拿一个小例子，画个表
确定“状态”的原则:
寻找变化信息
- abcd, ac (ac)=>abcde, ace (ace)
- 两个子串的长度是变化的，内容是固定的
确定“最优子结构”的原则: 寻找代表
- 同样的两个子串，能组成很多公共子序列
- 只关心最大长度，不关心具体长什么样
确定“阶段”的原则:线性增长的轮廓
- “轮廓”是已计算区域与未计算区域的分界
确定“决策”的原则:人工模拟时考虑了哪些选项?
f[i, j] 表示text1的前i 个字符和text2 的前j个字符能组成的LCS的长度
如果text1[i]=text2[j]: f[i, j]= f[i-1,j-1]+1
如果text1[i]≠text2[j]: f[i, j]= max(f [i一1,j],f [i,j一1])
动规题目的边界处理技巧
方法一:
f[0,0]=0，然后递推时用if语句判断，目标f [n - 1,m -1]
方法二:
认为字符串下标从1开始，f[i,0]=0与f[0,j]=0均作为边界，目标f[n, m]
300.最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/
class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int f[] = new int[n]; int pre[] = new int[n]; for(int i = 0; i < n; i++) { f[i] = 1; pre[i] = -1; } for(int i = 1; i < n; i++) for(int j = 0; j < i; j++) if(nums[j] < nums[i] && f[i] < f[j] + 1){ f[i] = f[j] + 1; pre[i] = j; } int ans = 0; int end = -1; for(int i = 0; i < n; i++) if(f[i] > ans) { ans = f[i]; end = i; } print(nums, pre, end); return ans; } void print(int[] nums, int[] pre, int i){ if(pre[i] != -1) print(nums, pre, pre[i]); System.out.println(nums[i]); } }
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); vector<int> dp(n,1); int max_k=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(nums[i]>nums[j]){ dp[i]=max(dp[j]+1,dp[i]); max_k=max(max_k,dp[i]); } } } return max_k; } };
动态规划解题步骤
动态规划“轮廓变化”
动态规划打印方案
动态规划题目打印方案的原则:记录转移路径＋递归输出
动态规划选取“代表”，维护了一个最优子结构
如果记录每个最优子结构的详细方案，时间复杂度会上升
以LCS为例，本来是0(len2)，每个opt[i,j]记录一个方案（字符串），就变成了0(len3)
正确做法:
记录每个f[i,j]是从哪里转移过来的(f[i-1,j]，fLi,j-1]还是f[i一1,j一1])
整个动规完成，求出f [n,m]后，再从(n,m)开始递归复原最优路径
53.最大子数组和
https://leetcode.cn/problems/maximum-subarray/
class Solution { public: int maxSubArray(vector<int>& nums) { // int pre = 0, maxAns = nums[0]; // for (const auto &x: nums) { // pre = max(pre + x, x); // maxAns = max(maxAns, pre); // } // return maxAns; int n=nums.size(); vector<int> dp(n+1,0); dp[0]=nums[0]; int mmax=dp[0]; for(int i=1;i<n;i++) { dp[i]=max(nums[i],dp[i-1]+nums[i]); mmax=max(mmax,dp[i]); } return mmax; } };
f[i]表示以i为结尾的最大子序和
f[i]=max(f [i -1]+mums[i], nums[i])
状态中何时需要“包含结尾”?
–当结尾参与判定条件时，例如LIS中a[j]
152.乘积最大子数组
https://leetcode.cn/problems/maximum-product-subarray/
class Solution { public: int maxProduct(vector<int>& nums) { vector <int> maxF(nums), minF(nums); for (int i = 1; i < nums.size(); ++i) { maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i])); minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i])); } return *max_element(maxF.begin(), maxF.end()); } };
70.爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/
class Solution { public: int climbStairs(int n) { int p = 0, q = 0, r = 1; for (int i = 1; i <= n; ++i) { p = q; q = r; r = p + q; } return r; } };
120.三角形最小路径和
https://leetcode.cn/problems/triangle/description/
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); vector<vector<int>> f(n, vector<int>(n)); f[0][0] = triangle[0][0]; for (int i = 1; i < n; ++i) { f[i][0] = f[i - 1][0] + triangle[i][0]; for (int j = 1; j < i; ++j) { f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]; } f[i][i] = f[i - 1][i - 1] + triangle[i][i]; } return *min_element(f[n - 1].begin(), f[n - 1].end()); } };
673.最长递增子序列的个数
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
class Solution { int binarySearch(int n, function<bool(int)> f) { int l = 0, r = n; while (l < r) { int mid = (l + r) / 2; if (f(mid)) { r = mid; } else { l = mid + 1; } } return l; } public: int findNumberOfLIS(vector<int> &nums) { vector<vector<int>> d, cnt; for (int v : nums) { int i = binarySearch(d.size(), [&](int i) { return d[i].back() >= v; }); int c = 1; if (i > 0) { int k = binarySearch(d[i - 1].size(), [&](int k) { return d[i - 1][k] < v; }); c = cnt[i - 1].back() - cnt[i - 1][k]; } if (i == d.size()) { d.push_back({v}); cnt.push_back({0, c}); } else { d[i].push_back(v); cnt[i].push_back(cnt[i].back() + c); } } return cnt.back().back(); } };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
