1.做题通法1确定dp[i]的含义确定方式1.题目明确给出 2. 经验得出题目要求 3.分析问题时重复子问题2)状态转移方程即dp[i]?3初始化保证填表时不越界4填表顺序要保证填写当前状态时所需的前置状态均已知5返回结果题目要求状态表示注意一道题可能有不同的动态规划的解法2.例题体验例1最小花费爬楼梯https://leetcode.cn/problems/min-cost-climbing-stairs/解法一在了解题意后先确定dp[i]的含义这里我们不妨就让dp[i]表示到达i位置时的最小消费~随后写状态转移方程取最邻近的一步到达i位置有两种方式从i-1和i-2位置出发并加上其消费取最小值直观一些表示就是所以状态转移方程就是dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);随后进行初始化根据题意dp[0]dp[1]0;下面我们看代码编写完成通过解法二我们也可以从另一个角度思考问题即让dp[i]表示从i位置出发到楼顶的最小花费也就是倒着想问题倒着填表~编写状态转移方程从i位置出发有两种选择1走一步之后从i1位置出发到楼顶的最小花费即cost[i]dp[i1]2走两步之后从i2位置出发到楼顶的最小花费即cost[i]dp[i2]3取二者最小值填入表中初始化dp[n-1]cost[n-1] , dp[n-2]cost[n-2]返回值由于我们是倒着填表的所以要比较一下dp[0]和dp[1]哪个最小代码编写完成例2不同路径https://leetcode.cn/problems/unique-paths-ii/还是先明确dp[i][j]含义走到[i][j]位置时的路径方法数接着得出状态转移方程不难发现[i][j]位置的方法数等于[i-1][j]位置和[i][j-1]位置方法数之和即dp[i][j]dp[i-1][j]dp[i][j-1]接着初始化dp表一种方式是这样初始化dp表的下标和数组的下标一一对应但是这样初始化太麻烦了得两个for循环所以我们可以引入虚拟表来初始化说白了就是在前面增加一行一列初始化时就把dp[0][1]初始化为1就好dp[1][0]初始化为1也行随后要注意下标映射关系整体右下移动一格举个例子如果[i][j]位置有障碍物那么对应的是dp[i1][j1]0!之后确定填表顺序编写代码参考代码class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int mobstacleGrid.size(),nobstacleGrid[0].size(); vectorvectorint dp(m1,vectorint(n1)); dp[1][0]1; for(int i1;im;i) { for(int j1;jn;j) { if(obstacleGrid[i-1][j-1]!1) //注意dp表与原二维数组下标的映射关系dp的所有下标都向右下移动一位 dp[i][j]dp[i-1][j]dp[i][j-1]; } } return dp[m][n]; } };完成~例3地下城游戏https://leetcode.cn/problems/dungeon-game/我们还是先尝试确定dp[i][j]按照之前的经验我们可以以某个位置为结尾设定dp[i][j]为从起点触发到达【ij】位置的时候的最低健康值但是经过实操发现写不出状态转移方程因为这点的最低健康值是取决于整条路径的会一直变变变写不了所以尝试第二条以某个位置为起点设定dp[i][j]为从【ij】位置出发到达终点所需的最低健康值发现可以填表顺序为从下向上、从右往左填下面推到状态转移方程我们假设到[i,j]位置最小血量为dp[i][j]其加上这里的血包应该大于等于下一个位置的最小生命值所以写出方程dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j];要注意的细节就是当dp[i][j]0时此时来到这个格子就死了来不及吃血包所以当其小于零是要手动设为1随后初始化就Ok参考代码class Solution { public: int calculateMinimumHP(vectorvectorint dungeon) { int mdungeon.size(),ndungeon[0].size(); vectorvectorint dp(m1,vectorint(n1, INT_MAX)); dp[m][n-1]dp[m-1][n]1; for(int im-1;i0;i--) { for(int jn-1;j0;j--) { dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j]; if(dp[i][j]0)//血量0时还没吃这个大血包呢就死了 dp[i][j]1; } } return dp[0][0]; } };二、简单多状态dp例4打家劫舍https://leetcode.cn/problems/house-robber-ii/做这道题时我们发现一个状态方程表示不了了这是个多状态的dp问题所以我们可以用两个dp来求解本题中我们假设f[i]为偷该房子所获取的总的最大金额g[i]表示不偷该房子所获取的总的最大金额在分析时发现第一间偷不偷会影响结果则应该对其进行分类讨论之后求最大值而剩下的房子间数则用打家劫舍1的方法解决就好这里不多写了参考代码class Solution { public: int rob(vectorint nums) { int nnums.size(); //第一间房子偷 int xnums[0]rob1(nums,2,n-2); //第一间房子不偷 int yrob1(nums,1,n-1); return max(x,y); } int rob1(vectorint nums,int left,int right) { if(leftright) return 0; vectorint f(nums.size()); auto gf; f[left]nums[left]; for(int ileft1;iright;i) { f[i]g[i-1]nums[i]; g[i]max(g[i-1],f[i-1]); } return max(g[right],f[right]); } };例5买卖股票https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/分析这个题时我们会发现有多种情况和状态了如第i天可能是买入或者卖出状态那么此时有两种设计dp表的方法下面都来介绍一下我们先分析题目明确有几种状态之后再画出状态机示意图这样可以保证我们一个情况都不落的分析出状态转移方程特别是复杂情景时对于本题状态机为这里我们用0表示买入1表示卖出随后得出状态转移方程法一用两个变量f,g来解决问题由状态机求出f[i]和g[i]的状态方程如下图所示最后根据f,g的实际物理意义来进行初始化f(0)-price[0],g(0)0;之后编写代码class Solution { public: int maxProfit(vectorint prices, int fee) { int mprices.size(); vectorint f(m); auto gf; //初始化 f[0]-prices[0],g[0]0; //填dp表 for(int i1;im;i) { f[i]max(f[i-1],g[i-1]-prices[i]); g[i]max(g[i-1],f[i-1]prices[i]-fee); } return max(f[m-1],g[m-1]); } };法二用一个二维dp来解决问题还是求出状态转移方程编写代码class Solution { public: int maxProfit(vectorint prices, int fee) { int mprices.size(); vectorvectorint dp(m,vectorint(2)); //0:买入有股票 1卖出无股票 //初始化 dp[0][0]-prices[0]; dp[0][1]0; for(int i1;im;i) { dp[i][0]max(dp[i-1][0],dp[i-1][1]-prices[i]); dp[i][1]max(dp[i-1][1],dp[i-1][0]prices[i]-fee); } return max(dp[m-1][0],dp[m-1][1]); } };例6买卖股票https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/本题重点是了解一种新的初始化方式这个题加了限制条件所以我们的状态表示也应该进行调整在本题目中交易次数和股票状态一直在变再外加上天数的变化得三元Vector了太复杂了这里我们可以采用两个dp表来进行解决之后根据状态机写出状态转移方程但是这里有个细节问题如果j1时他会越界啊况且此时物理意义根本不存在所以再写g[i]时可以先写成g[i-1][j]之后当i1时再写出上式。随后是初始化由于是最大值我一开始是想直接初始化为INT_MAX来着但是这样在-Price[i]时就会越界所以我们可以初始化为无穷小的一半即0x3f3f3f之后f[0][0]-p[0],g[0][0]0;代码class Solution { public: const int INF0x3f3f3f; int maxProfit(vectorint prices) { int mprices.size(); vectorvectorint f(m,vectorint(3,-INF)); auto gf; //初始化 f[0][0]-prices[0]; g[0][0]0; for(int i1;iprices.size();i) { for(int j0;j3;j) { f[i][j]max(f[i-1][j],g[i-1][j]-prices[i]); g[i][j]g[i-1][j]; if(j1) { g[i][j]max(g[i-1][j],f[i-1][j-1]prices[i]); } } } int ret0; for(int j0;j3;j) retmax(ret,g[m-1][j]); return ret; } };三、子数组问题(连续例6最长湍流子数组https://leetcode.cn/problems/longest-turbulent-subarray/这个题有两种方法可以解决都分享一下一种是一个dp表做一下另一种是两个dp表做一下其实思路都是一样的只是老师讲得是第二种说第一种做不出来我跟老师叫上真了非要用一个dp表做结果死磕半天搞出来了这里都给大家分享一下~法一一个dp表我们让dp[i]表示以i为结尾的最大湍流子数组的长度根据湍流定义我们写出状态进入条件以及状态转移方程之后要额外考虑一下整个数组都是一样大的情况这个简单看一下得了感觉参考意义不大要说唯一的意义就是学会了怎么判断一个vector里面的元素是否都相同~class Solution { public: int maxTurbulenceSize(vectorint arr) { int n arr.size(); vectorint dp(n, 2); //防止全是一样的数字 setint s; for (auto e : arr) s.insert(e); if (s.size() 1) return 1; if (n 2) return n; dp[0] 1, dp[1] 2; int ret 2; for (int i 2; i n; i) { bool sit1 (arr[i] arr[i - 1]) (arr[i - 1] arr[i - 2]); bool sit2 (arr[i] arr[i - 1]) (arr[i - 1] arr[i - 2]); bool current (sit1 || sit2); //先降后升 先升后降 if (current true) { //符合要求 dp[i] dp[i - 1] 1; ret max(ret, dp[i]); } if (arr[i] arr[i - 1]) { dp[i] 1; } } return ret; } };法二两个dp表老师的方法就明显清晰很多是这样解决的参考代码class Solution { public: int maxTurbulenceSize(vectorint arr) { int narr.size(); vectorint f(n,1); auto gf; int ret1; for(int i1;in;i) { if(arr[i]arr[i-1]) f[i]g[i-1]1; else if(arr[i]arr[i-1]) g[i]f[i-1]1; retmax(ret,max(f[i],g[i])); } return ret; } };例7拆分单词https://leetcode.cn/problems/word-break/这个题拿到这篇博客里完全就是因为我之前没见过这种字符串的刚拿到手完全蒙的一批现在总结一下这种题的经验首先这个就不能像是之前的数组那样一个for循环走到哪就dp到哪里了这个得两层用于锁住下一个要查找的单词就是i走在前面j来个回手掏区段j,i)组成的单词看wordlist有没有有就dp[i]搞成true在初始化上由于大多数的dp[i]都是false我们在初始化时就可以将其初始化为false,之后dp[0]必须设为true,因为如果要是false的话那后面全是false了因为状态转移方程为dp[i]dp[j-1]hash.count(substr(j,i-j1)),既然设了虚拟结点那就要注意映射关系由于这个是字符串我们直接在前面加个“ ”下标就和dp的一一映射了。参考代码class Solution { public: bool wordBreak(string str, vectorstring wordDict) { unordered_setstring s; for(autoe:wordDict) { s.insert(e); } int nstr.size(); vectorbool dp(n1,false); dp[0]true; str str; for(int i1;in;i) { for(int ji;j1;j--) { if(dp[j-1]trues.count(str.substr(j,i-j1))) dp[i]true; } } return dp[n]; } };四、子序列问题(不连续例8最长数对链https://leetcode.cn/problems/maximum-length-of-pair-chain/这个题不好搞的一点就是我们要是直接dp的话那我填写dp[i]的时候可能还要用到dp[i]后面的dp值这个在动态规划里面是万万不可的所以我们先进行排序之后再做。下面为解题思路不打字了节约时间~参考代码class Solution { public: int findLongestChain(vectorvectorint pairs) { sort(pairs.begin(),pairs.end()); int npairs.size(); vectorint dp(n,1); int ret1; for(int i1;in;i) { for(int j0;ji;j) { if(pairs[j][1]pairs[i][0]) dp[i]max(dp[i],dp[j]1); } retmax(ret,dp[i]); } return ret; } };例9最长递增子序列的个数https://leetcode.cn/problems/number-of-longest-increasing-subsequence/这个题让我们找最长递增子序列的个数我一开始想只用一个dp来着但是发现连最长长度都统计不了那咋更新结果啊得比较最长长度才能求出个数啊所以我果断采用两个dp表一个用于统计最长长度len[i]一个用于统计这个最长长度的子序列的个数count[i]这里我们可以用一个小贪心算法就是如何用一次for循环找出这个数组的最大值做法就是初始化Maxvalarr[0],count0;之后遍历数组大于maxval就count置为1重新计数maxval也改为这个值要是等于maxval就count我们再回到本题之后写状态转移方程参考代码class Solution { public: int findNumberOfLIS(vectorint nums) { int nnums.size(); vectorint len(n,1); auto countlen; int retlen1,retcount1; for(int i1;in;i) { for(int j0;ji;j) { if(nums[j]nums[i]) { if(len[j]1len[i]) count[i]count[j]; else if(len[j]1len[i])//重新计数 len[i]len[j]1,count[i]count[j]; } } if(retlenlen[i]) retcountcount[i]; else if(retlenlen[i]) retlenlen[i],retcountcount[i]; } return retcount; } };例10最长定差子序列(哈希表做动态规划)https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/这道题收录的原因就是很新颖其难度不大就是使用哈希表作为dp表进行动态规划我们先看传统的dp方法会超时class Solution { public: int longestSubsequence(vectorint arr, int difference) { int narr.size(); vectorint dp(n,1); int ret1; for(int i1;in;i) { for(int j0;ji;j) { if(arr[j]differencearr[i]) { dp[i]dp[j]1; retmax(ret,dp[i]); } } } return ret; } };我们来看哈希表的做法利用哈希表来将arr[i]的值和dp[i]的值建立映射因为difference是固定的所以arr[i]-difference也是固定的要找这个dp值时直接去哈希表里面找就完了~class Solution { public: int longestSubsequence(vectorint arr, int difference) { int narr.size(); unordered_mapint,int hash(n); //arr[i]-dp[i] hash[arr[0]]1; //初始化 int ret1; for(int i1;iarr.size();i) { hash[arr[i]]hash[arr[i]-difference]1; retmax(ret,hash[arr[i]]); } return ret; } };例11最长的斐波那契子序列的长度https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/选这个题的重要因素是其dp的设置很新颖我们尝试做一下时假设dp[i]表示以i为最后一个斐波那契数时我们根本写不出状态转移方程因为这个数列是由三个数组成的只知道一个没有用于是我们换一种写法让dp[i][j]表示以i位置和j位置为结尾的子序列中斐波那契数列的最长长度之后进行分析就好了~参考代码class Solution { public: int lenLongestFibSubseq(vectorint arr) { int narr.size(); unordered_mapint,int hash; for(int i0;in;i) { hash[arr[i]]i; } int ret2; vectorvectorint dp(n,vectorint(n,2)); for(int j2;jn;j) { for(int i1;ij;i) { int aarr[j]-arr[i]; if(aarr[i]hash.count(a)) { dp[i][j]dp[hash[a]][i]1; } retmax(ret,dp[i][j]); } } if(ret3) return 0; else return ret; } };五、回文串问题例11回文子串https://leetcode.cn/problems/palindromic-substrings/这个我一开始是想的dp[i]表示以i位置为结尾的回文串的个数但是发现写不出方程于是就只能换成二维了dp[i][j]表示从[i,j]的字符串是否回文状态转移方程如下图进行分类讨论代码编写class Solution { public: int countSubstrings(string s) { int ns.size(); vectorvectorbool dp(n,vectorbool(n,false)); int cnt0; for(int in-1;i0;i--) { for(int ji;jn;j) { if(s[i]s[j]) { if(i1j||ij) dp[i][j]true; if(i1j) dp[i][j]dp[i1][j-1]; } if(dp[i][j]true) cnt; } } return cnt; } };中间判断部分可以用三目表达式进行优化dp[i][j]i1j?dp[i1][j-1]:true;例12最长回文子串https://leetcode.cn/problems/longest-palindromic-substring/这个题跟上一个套路一样就是增加一个更新结果的变量就行之后直接substr参考代码class Solution { public: string longestPalindrome(string s) { int ns.size(); vectorvectorbool dp(n,vectorbool(n)); int len1,begin0; for(int in-1;i0;i--) { for(int ji;jn;j) { if(s[i]s[j]) dp[i][j]i1j?dp[i1][j-1]:true; if(dp[i][j] j-i1len) lenj-i1,begini; } } return s.substr(begin,len); } };例13 分割回文串 IV这个题让我们切割所以我们不妨就把其分成三段[0,i-1][i,j][j1,n],看着三段能不能同时构成回文即可所以我们就要把所有{ij]位置能不能构成回文串写出来代码跟上面差不多class Solution { //dp求出所有字符串是否为回文串 //在两层for看[0,i-1][i,j][j1,n]是否都为true public: bool checkPartitioning(string s) { int ns.size(); vectorvectorbool dp(n,vectorbool(n)); for(int in-1;i0;i--) { for(int ji;jn;j) { if(s[i]s[j]) dp[i][j]i1j?dp[i1][j-1]:true; } } for(int i1;in-1;i) { for(int ji;jn-1;j) { if(dp[0][i-1]dp[i][j]dp[j1][n-1]) return true; } } return false; } };例14分割回文串 II这个题我还是尝试用dp[i]表示以i位置为结尾时的最少分割次数随后对区间[0,i]进行讨论这里我们判断是否回文时可以直接利用上面求会回文的方法~class Solution { public: int minCut(string s) { int ns.size(); vectorvectorbool isPal(n,vectorbool(n)); for(int in-1;i0;i--) { for(int ji;jn;j) { if(s[i]s[j]) isPal[i][j]i1j?isPal[i1][j-1]:true; } } vectorint dp(n,INT_MAX); for(int i0;in;i) { if(isPal[0][i]) dp[i]0; else { for(int ji;j0;j--) { if(isPal[j][i]) { dp[i]min(dp[j-1]1,dp[i]); } } } } return dp[n-1]; } };例15: 最长回文子序列这个题是子序列(不连续),解决方法跟上面的差不多~这里把老师的图拿过来吧我自己画的有点抽象上不了台面思路都差不多结合题意看一下就懂了~参考代码class Solution { public: int longestPalindromeSubseq(string s) { int ns.size(); vectorvectorint dp(n,vectorint(n)); dp[0][0]1,dp[n-1][n-1]1; for(int in-1;i0;i--) { for(int ji;jn;j) { if(s[i]s[j]) { if(ij) dp[i][j]1; else if(i1j) dp[i][j]2; else dp[i][j]dp[i1][j-1]2; } else dp[i][j]max(dp[i][j-1],dp[i1][j]); } } return dp[0][n-1]; } };六、两个数组的 dp例16最长公共子序列这个题我一开始只用dp[i]表示什么发现表示不了所以换成二维的dp[i][j]表示s1的[0,i]区间和s2[0,j]区间的最长公共子序列随后写状态转移方程分类讨论当s1[i]s2[j]时dp[i][j]dp[i-1][j-1]1;当s1[i]!s2[j]时dp[i][j]max(dp[i][j-1],max(dp[i-1][j-1],dp[i-1][j]))之后看边界有越界情况所以加上虚拟节点并根据题意和dp值初始化为0记得注意下表映射关系对于字符串来说本题可以在字符串前面加上一个空格这样dp表和字符串就是一一对应的了~两种代码都会给出~正常解法class Solution { public: int longestCommonSubsequence(string text1, string text2) { int ntext1.size(),mtext2.size(); vectorvectorint dp(n1,vectorint(m1)); for(int i1;in;i) { for(int j1;jm;j) { if(text1[i-1]text2[j-1]) dp[i][j]dp[i-1][j-1]1; else dp[i][j]max(dp[i][j-1],max(dp[i-1][j-1],dp[i-1][j])); } } return dp[n][m]; } };针对字符串的特殊解法class Solution { public: int longestCommonSubsequence(string text1, string text2) { int ntext1.size(),mtext2.size(); text1 text1,text2 text2; vectorvectorint dp(n1,vectorint(m1)); for(int i1;in;i) { for(int j1;jm;j) { if(text1[i]text2[j]) dp[i][j]dp[i-1][j-1]1; else dp[i][j]max(dp[i][j-1],max(dp[i-1][j-1],dp[i-1][j])); } } return dp[n][m]; } };七、背包问题一、什么是背包问题背包问题是动态规划中的经典模型。基本描述有 n 件物品每件物品有体积 v[i] 和价值 w[i]。有一个容量为 V 的背包。问如何选择物品使总价值最大。根据“物品是否可以重复选取”背包问题可以分为类型特点01 背包每件物品只能选 1 次完全背包每件物品可以选无限次多重背包每件物品有数量限制分组背包每组只能选一个二、01 背包问题例17模板背包https://www.nowcoder.com/share/jump/4557712421772035627006我们讨论的是 01 背包前 i 件物品背包容量为 j最大价值是多少对于第 i 件物品你只有两种选择选和不选这是整个状态转移的根本来源。我们定义dp[i][j]表示前 i 件物品在容量为 j 时的最大价值。注意两个关键点“前 i 件”、“容量为 j”现在我们要算 dp[i][j]。考虑第 i 件物品情况 1不选第 i 件那价值就等于前 i-1 件物品在容量 j 时的最大价值也就是dp[i-1][j]情况 2选第 i 件能选的前提是什么 j v[i]选了之后占用体积 v[i]还剩 j - v[i] 容量还可以从前 i-1 件物品中选择所以价值是dp[i-1][j-v[i]] w[i]所以dp[i][j] max(dp[i-1][j],dp[i-1][j-v[i]] w[i])初始化就根据实际物理意义搞就好了参考代码#include cstring #include iostream using namespace std; const int N1010; int n,V,v[N],w[N]; int dp[N][N]; int main() { cinnV; for(int i1;in;i) cinv[i]w[i]; //开始dp //第一问 for(int i1;in;i) { for(int j0;jV;j) { dp[i][j]dp[i-1][j]; if(jv[i]) dp[i][j]max(dp[i-1][j-v[i]]w[i],dp[i-1][j]); } } coutdp[n][V]endl; //第二问 memset(dp, 0, sizeof dp); for(int j1;jV;j) dp[0][j]-1; for(int i1;in;i) { for(int j0;jV;j) { dp[i][j]dp[i-1][j]; if(jv[i]dp[i-1][j-v[i]]!-1) dp[i][j]max(dp[i-1][j-v[i]]w[i],dp[i-1][j]); } } cout(dp[n][V]-1?0:dp[n][V])endl; return 0; }