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）走一步，之后从i+1位置出发，到楼顶的最小花费，即cost[i]+dp[i+1]

2）走两步，之后从i+2位置出发，到楼顶的最小花费，即cost[i]+dp[i+2]

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[i+1][j+1]=0!

之后确定填表顺序，编写代码

参考代码：

class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size(),n=obstacleGrid[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); dp[1][0]=1; for(int i=1;i<=m;i++) { for(int j=1;j<=n;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]为从起点触发，到达【i，j】位置的时候的最低健康值，但是经过实操发现，写不出状态转移方程，因为这点的最低健康值是取决于整条路径的，会一直变变变，写不了

所以尝试第二条，以某个位置为起点，设定dp[i][j]为从【i，j】位置出发，到达终点，所需的最低健康值，发现可以，填表顺序为从下向上、从右往左填，下面推到状态转移方程

我们假设到[i,j]位置最小血量为dp[i][j]，其加上这里的血包，应该大于等于下一个位置的最小生命值，所以写出方程，dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];

要注意的细节就是当dp[i][j]<=0时，此时来到这个格子就死了，来不及吃血包，所以当其小于零是要手动设为1，随后初始化就Ok

参考代码：

class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int m=dungeon.size(),n=dungeon[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1, INT_MAX)); dp[m][n-1]=dp[m-1][n]=1; for(int i=m-1;i>=0;i--) { for(int j=n-1;j>=0;j--) { dp[i][j]=min(dp[i+1][j],dp[i][j+1])-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(vector<int>& nums) { int n=nums.size(); //第一间房子偷 int x=nums[0]+rob1(nums,2,n-2); //第一间房子不偷 int y=rob1(nums,1,n-1); return max(x,y); } int rob1(vector<int>& nums,int left,int right) { if(left>right) return 0; vector<int> f(nums.size()); auto g=f; f[left]=nums[left]; for(int i=left+1;i<=right;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(vector<int>& prices, int fee) { int m=prices.size(); vector<int> f(m); auto g=f; //初始化 f[0]=-prices[0],g[0]=0; //填dp表 for(int i=1;i<m;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(vector<int>& prices, int fee) { int m=prices.size(); vector<vector<int>> dp(m,vector<int>(2)); //0:买入（有股票） 1：卖出（无股票） //初始化 dp[0][0]=-prices[0]; dp[0][1]=0; for(int i=1;i<m;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表来进行解决：

之后根据状态机写出状态转移方程：

但是这里有个细节问题，如果j<1时他会越界啊，况且此时物理意义根本不存在，所以再写g[i]时，可以先写成g[i-1][j]，之后当i>=1时再写出上式。

随后是初始化，由于是最大值，我一开始是想直接初始化为INT_MAX来着，但是这样在+-Price[i]时就会越界，所以我们可以初始化为无穷小的一半，即0x3f3f3f，之后f[0][0]=-p[0],g[0][0]=0;

代码：

class Solution { public: const int INF=0x3f3f3f; int maxProfit(vector<int>& prices) { int m=prices.size(); vector<vector<int>> f(m,vector<int>(3,-INF)); auto g=f; //初始化 f[0][0]=-prices[0]; g[0][0]=0; for(int i=1;i<prices.size();i++) { for(int j=0;j<3;j++) { f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]); g[i][j]=g[i-1][j]; if(j>=1) { g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i]); } } } int ret=0; for(int j=0;j<3;j++) ret=max(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(vector<int>& arr) { int n = arr.size(); vector<int> dp(n, 2); //防止全是一样的数字 set<int> 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(vector<int>& arr) { int n=arr.size(); vector<int> f(n,1); auto g=f; int ret=1; for(int i=1;i<n;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; ret=max(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-j+1)),

既然设了虚拟结点，那就要注意映射关系，由于这个是字符串，我们直接在前面加个“ ”，下标就和dp的一一映射了。

参考代码：

class Solution { public: bool wordBreak(string str, vector<string>& wordDict) { unordered_set<string> s; for(auto&e:wordDict) { s.insert(e); } int n=str.size(); vector<bool> dp(n+1,false); dp[0]=true; str=" "+str; for(int i=1;i<=n;i++) { for(int j=i;j>=1;j--) { if(dp[j-1]==true&&s.count(str.substr(j,i-j+1))) 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(vector<vector<int>>& pairs) { sort(pairs.begin(),pairs.end()); int n=pairs.size(); vector<int> dp(n,1); int ret=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(pairs[j][1]<pairs[i][0]) dp[i]=max(dp[i],dp[j]+1); } ret=max(ret,dp[i]); } return ret; } };

例9：最长递增子序列的个数

https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

这个题让我们找最长递增子序列的个数，我一开始想只用一个dp来着，但是发现连最长长度都统计不了，那咋更新结果啊？得比较最长长度才能求出个数啊，所以我果断采用两个dp表，一个用于统计最长长度len[i]，一个用于统计这个最长长度的子序列的个数count[i]，

这里我们可以用一个小贪心算法，就是如何用一次for循环，找出这个数组的最大值，做法就是初始化Maxval=arr[0],count=0;之后遍历数组，大于maxval就count置为1重新计数，maxval也改为这个值，要是等于maxval就count++

我们再回到本题，之后写状态转移方程，

参考代码：

class Solution { public: int findNumberOfLIS(vector<int>& nums) { int n=nums.size(); vector<int> len(n,1); auto count=len; int retlen=1,retcount=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(nums[j]<nums[i]) { if(len[j]+1==len[i]) count[i]+=count[j]; else if(len[j]+1>len[i])//重新计数 len[i]=len[j]+1,count[i]=count[j]; } } if(retlen==len[i]) retcount+=count[i]; else if(retlen<len[i]) retlen=len[i],retcount=count[i]; } return retcount; } };

例10：最长定差子序列

(哈希表做动态规划)

https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

这道题收录的原因就是很新颖，其难度不大，就是使用哈希表作为dp表进行动态规划，我们先看传统的dp方法，会超时：

class Solution { public: int longestSubsequence(vector<int>& arr, int difference) { int n=arr.size(); vector<int> dp(n,1); int ret=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(arr[j]+difference==arr[i]) { dp[i]=dp[j]+1; ret=max(ret,dp[i]); } } } return ret; } };

我们来看哈希表的做法：

利用哈希表来将arr[i]的值和dp[i]的值建立映射，因为difference是固定的，所以arr[i]-difference也是固定的，要找这个dp值时，直接去哈希表里面找就完了~

class Solution { public: int longestSubsequence(vector<int>& arr, int difference) { int n=arr.size(); unordered_map<int,int> hash(n); //arr[i]-dp[i] hash[arr[0]]=1; //初始化 int ret=1; for(int i=1;i<arr.size();i++) { hash[arr[i]]=hash[arr[i]-difference]+1; ret=max(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(vector<int>& arr) { int n=arr.size(); unordered_map<int,int> hash; for(int i=0;i<n;i++) { hash[arr[i]]=i; } int ret=2; vector<vector<int>> dp(n,vector<int>(n,2)); for(int j=2;j<n;j++) { for(int i=1;i<j;i++) { int a=arr[j]-arr[i]; if(a<arr[i]&&hash.count(a)) { dp[i][j]=dp[hash[a]][i]+1; } ret=max(ret,dp[i][j]); } } if(ret<3) 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 n=s.size(); vector<vector<bool>> dp(n,vector<bool>(n,false)); int cnt=0; for(int i=n-1;i>=0;i--) { for(int j=i;j<n;j++) { if(s[i]==s[j]) { if(i+1==j||i==j) dp[i][j]=true; if(i+1<j) dp[i][j]=dp[i+1][j-1]; } if(dp[i][j]==true) cnt++; } } return cnt; } };

中间判断部分可以用三目表达式进行优化：dp[i][j]=i+1<j?dp[i+1][j-1]:true;

例12：最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

这个题跟上一个套路一样，就是增加一个更新结果的变量就行，之后直接substr

参考代码：

class Solution { public: string longestPalindrome(string s) { int n=s.size(); vector<vector<bool>> dp(n,vector<bool>(n)); int len=1,begin=0; for(int i=n-1;i>=0;i--) { for(int j=i;j<n;j++) { if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true; if(dp[i][j]&& j-i+1>len) len=j-i+1,begin=i; } } return s.substr(begin,len); } };

例13： 分割回文串 IV

这个题让我们切割，所以我们不妨就把其分成三段，[0,i-1][i,j][j+1,n],看着三段能不能同时构成回文即可，所以我们就要把所有{i，j]位置能不能构成回文串写出来，代码跟上面差不多：

class Solution { //dp求出所有字符串是否为回文串 //在两层for看[0,i-1][i,j][j+1,n]是否都为true public: bool checkPartitioning(string s) { int n=s.size(); vector<vector<bool>> dp(n,vector<bool>(n)); for(int i=n-1;i>=0;i--) { for(int j=i;j<n;j++) { if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true; } } for(int i=1;i<n-1;i++) { for(int j=i;j<n-1;j++) { if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true; } } return false; } };

例14：分割回文串 II

这个题我还是尝试用dp[i]表示以i位置为结尾时的最少分割次数，随后对区间[0,i]进行讨论，

这里我们判断是否回文时，可以直接利用上面求会回文的方法~

class Solution { public: int minCut(string s) { int n=s.size(); vector<vector<bool>> isPal(n,vector<bool>(n)); for(int i=n-1;i>=0;i--) { for(int j=i;j<n;j++) { if(s[i]==s[j]) isPal[i][j]=i+1<j?isPal[i+1][j-1]:true; } } vector<int> dp(n,INT_MAX); for(int i=0;i<n;i++) { if(isPal[0][i]) dp[i]=0; else { for(int j=i;j>=0;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 n=s.size(); vector<vector<int>> dp(n,vector<int>(n)); dp[0][0]=1,dp[n-1][n-1]=1; for(int i=n-1;i>=0;i--) { for(int j=i;j<n;j++) { if(s[i]==s[j]) { if(i==j) dp[i][j]=1; else if(i+1==j) dp[i][j]=2; else dp[i][j]=dp[i+1][j-1]+2; } else dp[i][j]=max(dp[i][j-1],dp[i+1][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 n=text1.size(),m=text2.size(); vector<vector<int>> dp(n+1,vector<int>(m+1)); 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][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 n=text1.size(),m=text2.size(); text1=" "+text1,text2=" "+text2; vector<vector<int>> dp(n+1,vector<int>(m+1)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;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 背包问题

例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 N=1010; int n,V,v[N],w[N]; int dp[N][N]; int main() { cin>>n>>V; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //开始dp //第一问 for(int i=1;i<=n;i++) { for(int j=0;j<=V;j++) { dp[i][j]=dp[i-1][j]; if(j>=v[i]) dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]); } } cout<<dp[n][V]<<endl; //第二问 memset(dp, 0, sizeof dp); for(int j=1;j<=V;j++) dp[0][j]=-1; for(int i=1;i<=n;i++) { for(int j=0;j<=V;j++) { dp[i][j]=dp[i-1][j]; if(j>=v[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; }