动态规划如何学习
参考灵神的视频和题解做的笔记（灵神YYDS，以后也都会用这套逻辑去思考）
动态规划入门：从记忆化搜索到递推_哔哩哔哩_bilibili
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
学习步骤：
1.思考递归回溯的暴力穷举法（即深度优先遍历DFS）
注意要画树形结构，画完很容易看出哪里是重复的计算，对改成记忆化搜索有好处
可以使用代码随想录的递归三部曲
2.改成记忆化搜索，就是准备一个备忘录数组，保存已经计算过的结果
3.把记忆化搜索1:1翻译成为DP
翻译的时候可以想想代码随想录的动规五部曲，其实到这里五部曲的内容已经全部解决了
刷了几道题以后的发现：
1.思考回溯的时候一般就会把dp数组和下标的含义给想清楚，这一过程就是分割子问题的过程，不然回溯想不出来的，一般而言，dp数组的含义就是题目要求的东西，什么最大价值，最小金额，方案数量都可能是dp数组的含义
2.回溯算法终止条件一般是dp数组的初始化
3.记忆化搜索一般是自底向上，和动态规划的从前往后其实是一样的，只是记忆化是递归里的栈，而动态规划是for循环
4.dfs函数就是dp数组
5.dfs一般传入的参数n在动态规划里面一般是一层for循环，dfs中如果有for循环，那动态规划的递推一般是两层循环，而且n可以和循环中的一个进行替换
6.如果根据回溯的终止条件判断出来是不需要进行初始化的，接下来要注意是不是有不合法的状态，一般而言不合法的状态都可以通过回溯里面的递推公式（一般在返回值的地方）推出来它应该等于多少，然后进行初始化。一般而言还会有另外的初始化方法，就比如让dp数组的下标+1或者+2，这里这么说大家不太理解，等下看看打家劫舍就明白了。
**动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。**在做题时，可根据题目要求，选择适合题目的一种来思考。
枚举选哪个
746.使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
第一步：回溯法（深度优先遍历）
这个过不了，时间复杂度太高，但是这是学习动态规划的必由之路
思路：
首先思考子问题并画出树形结构图
我们要求到第5个台阶的最小花费，我们可以从第4个加上4的花销上一个台阶，也可以从3加上3的花销上两个台阶
我们要求到第n个台阶的最小花费，我们可以从第n-1个加上n-1的花销上一个台阶，也可以从n-2加上n-2的花销上两个台阶，n-1就是下一个要求的子问题，由n-2和n-3得到，一直到1或2，它的花费就是0，因为可以选择从1或2开始爬楼梯
这样就得到了一个二叉树（以5为例子）
我们要到5的台阶，就要依靠到达4和到达3的结果，来比较得到最小值，所以要得到下层结点向上层返回的结果，那就得用后序遍历来得到4,3的结果
1.返回值和参数
我们要下层结点的最小值，所以要int
cost是题目中的花费数组，index是记录我们遍历到哪里了，相当于for循环里面的i
1
| int dfs(vector<int>& cost,int index)
|
2.终止条件
1
2
| if(index==0||index==1)
return 0;
|
0其实是第一个台阶，1其实是第二个台阶，因为cost数组从0开始。
爬第一个或第二个台阶不需要花费，所以直接返回0
3.本层逻辑
左子树返回爬上第n-1台阶的最小值
右子树返回爬上第n-2台阶的最小值
最后本层返回的就是两者的最小值作为结果
1
2
3
| int l=dfs(cost,index-1)+cost[index-1];
int r=dfs(cost,index-2)+cost[index-2];
return min(l,r);
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int dfs(vector<int>& cost,int index)
{
if(index==0||index==1)
return 0;
int l=dfs(cost,index-1)+cost[index-1];
int r=dfs(cost,index-2)+cost[index-2];
return min(l,r);
}
int minCostClimbingStairs(vector<int>& cost) {
return dfs(cost,cost.size());
}
};
|
C++还可用lambda来写
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
function<int(int)> dfs=[&](int index)->int{
if(index==0||index==1)
return 0;
return min(dfs(index-1)+cost[index-1],dfs(index-2)+cost[index-2]);
};
return dfs(cost.size());
}
};
|
第二步：改成记忆化搜索
从图中可以看到，这些地方就是重复计算的地方，可以直接砍掉。
怎么砍呢？
我们在遍历过程中，如果是第一次碰到这个数字呢，我们就把它的计算结果给保存到一个数组当中去，下次要用的话直接从数组里面拿而不用再次进行递归计算了。
砍完之后还剩下啥：只需要计算3,4,5，你会发现时间复杂度竟然变成了O(n)，成了线性的，那这不就和递推一样了么？用1,2计算3，用2,3计算4，用3,4计算5得出结果。
在递归进行记忆化搜索里面，这是自底向上的计算，算5，要去递归3,4，然后一层一层递归
到最后1和2的时候直接返回0，然后得出3的最小，然后根据2,3得出4的最小，最后一层一层返回知道最后。
下面就来看递推。
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int dfs(vector<int>& cost,vector<int>& dp,int index)
{
if(index==0||index==1)
return 0;
if(dp[index]!=-1)
return dp[index];
int l=dfs(cost,dp,index-1)+cost[index-1];
int r=dfs(cost,dp,index-2)+cost[index-2];
return dp[index]=min(l,r);
}
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+1,-1);
return dfs(cost,dp,cost.size());
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+1,-1);
function<int(int)> dfs=[&](int index)->int{
if(index==0||index==1)
return 0;
if(dp[index]!=-1)
return dp[index];
int& res=dp[index];
return res=min(dfs(index-1)+cost[index-1],dfs(index-2)+cost[index-2]);
};
return dfs(cost.size());
}
};
|
注意点：
1.传入的dp备忘录必须是引用传入，不然的话下层的结果保存不到数组里面，每一层的dp数组还全都是-1，就和DFS逻辑一样了其实。dp数组不会起到任何作用
2.对dp[index]一定要赋值，不能直接返回min(l,r)，不然dp数组不会更新
3.l和r不可以替换成dp[index-1]和dp[index-2]。（如果有小伙伴不幸和一样犯了这个错误，那就继续看吧）
1
2
3
| int dp[index-1]=dfs(cost,dp,index-1)+cost[index-1];
int dp[index-2]=dfs(cost,dp,index-2)+cost[index-2];
return dp[index]=min(l,r);
|
我先说答案：这种乍一看挺对的，实际上没有想清楚dfs返回值到底是什么，dfs（index-1）的返回值是dp[index-1]，如果再加上cost[index-1]，那得到的应该是dp[index]，而不是dp[index]。
下面是我没彻底弄懂之前写的，只是记录一下自己的思考过程，不想看的可以跳过了
这种方式会刷新我们已经保存过的dp[index]，就比如起始的0和1，dp[0]和dp[1]花费最小值本来都是0，但是用这个在计算dp[3]的时候会把dp[0]和dp[1]赋值为cost[0]和cost[1]。
然后dp[2]=dp[0]+cost[0]=2，可是我们一看这肯定是1怎么能是2呢？
后面的dp[3]也是最开始被更新为3，后面直接变成4了，这就是再次刷新了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 输入
cost =
[1,100,1,1,1,100,1,1,100,1]
标准输出
index=2
1 100 -1 -1 -1 -1 -1 -1 -1 -1 -1
index=3
1 100 2 -1 -1 -1 -1 -1 -1 -1 -1
index=4
1 100 3 3 -1 -1 -1 -1 -1 -1 -1
index=5
1 100 3 4 4 -1 -1 -1 -1 -1 -1
index=6
1 100 3 4 5 104 -1 -1 -1 -1 -1
index=7
1 100 3 4 5 204 6 -1 -1 -1 -1
index=8
1 100 3 4 5 204 7 7 -1 -1 -1
index=9
1 100 3 4 5 204 7 8 107 -1 -1
index=10
1 100 3 4 5 204 7 8 207 9 -1
|
正确的打印：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| cost =
[1,100,1,1,1,100,1,1,100,1]
标准输出
index=2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
index=3
-1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1
index=4
-1 -1 1 2 -1 -1 -1 -1 -1 -1 -1
index=5
-1 -1 1 2 2 -1 -1 -1 -1 -1 -1
index=6
-1 -1 1 2 2 3 -1 -1 -1 -1 -1
index=7
-1 -1 1 2 2 3 3 -1 -1 -1 -1
index=8
-1 -1 1 2 2 3 3 4 -1 -1 -1
index=9
-1 -1 1 2 2 3 3 4 4 -1 -1
index=10
-1 -1 1 2 2 3 3 4 4 5 -1
|
第三步：一比一翻译成动态规划(递推)
1.确定dp数组以及下标的含义
dp数组含义是登上第i个台阶由多少种方法
i下标就是第i+1个台阶
2.确定递推公式
1
| dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
|
这个就是在回溯的两个选择里面挑一个小的
就是记忆化搜索里面的返回值
3.dp数组如何初始化
就是回溯里面的终止条件
1
2
| vector<int> dp(cost.size()+1,-1);
dp[0]=0,dp[1]=0;
|
4.确定遍历顺序
后面的5要依靠前面3,4的计算结果，所以肯定是正向遍历
完整代码：
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+1,-1);
dp[0]=0,dp[1]=0;
for(int i=2;i<=cost.size();i++)
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
return dp[cost.size()];
}
};
|
优化
其实也不需要把所有的结果全都给记住，只需要记住i的前一个i-1（b）和前前一个i-2（a）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a=0,b=0;
for(int i=2;i<=cost.size();i++)
{
int c=min(a+cost[i-2],b+cost[i-1]);
a=b;
b=c;
}
return b;
}
};
|
选或不选
一、198.打家劫舍
198. 打家劫舍 - 力扣（LeetCode）
思路分析：
树形结构图
先明确一下dp数组/dfs函数的含义，dp[i]就是在前i个房子里面打家劫舍，能得到的最高金额（就是题目要求的）
我们从最后一个房子倒着往前分析子问题
对于一个房子i，我们只有两种方案，选或者不选
选了的话，那我i-1就不能选了
不选的话，那我前i个房子可以得到的最大金额数量就和前i-1个房子可以得到的最大金额数量相等，因为第i个房子没选
所以可以很轻易的得出
1
| dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
|
即在可能的两种方案中挑选一个最大值
1.回溯 DFS
1.返回值和参数
i是房子编号
nums是房子数字
dfs返回值就是前i个房子里面打家劫舍可以得到的最大金额（和dp数组含义相同）
1
| int dfs(int i,vector<int>& nums)
|
2.终止条件
可以看到我们递归到0就是叶子结点了，下标0是第一个房子，所以小于0就代表没有房子可以选了，没有房子可以选也就没有金额，就返回0
3.本层逻辑
如上所说，返回两者的最大值给上层递归函数就好
1
| return max(dfs(i-1,nums),dfs(i-2,nums)+nums[i]);
|
完整代码：
当然，这是超时的
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int dfs(int i,vector<int>& nums)
{
if(i<0)
return 0;
return max(dfs(i-1,nums),dfs(i-2,nums)+nums[i]);
}
int rob(vector<int>& nums) {
return dfs(nums.size()-1,nums);
}
};
|
2.记忆化搜索
就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int dfs(int i,vector<int>& nums,vector<int>& dp)
{
if(i<0)
return 0;
if(dp[i]!=-1)
return dp[i];
return dp[i]=max(dfs(i-1,nums,dp),dfs(i-2,nums,dp)+nums[i]);
}
int rob(vector<int>& nums) {
vector<int> dp(nums.size(),-1);
return dfs(nums.size()-1,nums,dp);
}
};
|
3.1:1翻译为动态规划
1.确定dp数组以及下标的含义
dp数组就是前i个房子里面可以取得的最大金额
下标就是房子编号
2.确定递推公式
忘记了原因的请看思路分析部分
1
| dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
|
3.dp数组如何初始化
第一种写法，dp数组的下标从0开始，在i=0和i=1我们的递推公式中会有不合法的状态，所以i需要从2开始
那么dp[0]和dp[1]就需要初始化，那么初始化为多少呢？
如果可以根据dp的含义想通如何初始化是最好的，比如前1间房子最大值就是nums[0]，前两间房子最大值就是max(nums[0],nums[1])
如果想不通的话，回到回溯法把0和1带进去就完事得出结果就完事
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int dfs(int i,vector<int>& nums)
{
if(i<0)
return 0;
return max(dfs(i-1,nums),dfs(i-2,nums)+nums[i]);
}
int rob(vector<int>& nums) {
return dfs(nums.size()-1,nums);
}
};
|
会得到如下的初始化方案：
1
2
3
4
5
6
| vector<int> dp(nums.size(),0);
dp[0]=nums[0];
if(nums.size()>1)
dp[1]=max(nums[0],nums[1]);
else
return dp[0];
|
第二种写法
dp数组的下标全部都+2（注意nums数组的下标是没变的，此时dp数组的2对应的是nums的0）
这样就避免了下标是负数的情况，完美贴合了dfs回溯的方法
1
2
3
| vector<int> dp(nums.size()+2,0);
for(int i=0;i<nums.size();i++)
dp[i+2]=max(dp[i+1],dp[i]+nums[i]);
|
4.确定遍历顺序
后续结果需要依赖前面的计算结果，故使用从前往后遍历
1
2
| for(int i=2;i<nums.size();i++)
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size(),0);
dp[0]=nums[0];
if(nums.size()>1)
dp[1]=max(nums[0],nums[1]);
else
return dp[0];
for(int i=2;i<nums.size();i++)
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
return dp[nums.size()-1];
}
};
|
1
2
3
4
5
6
7
8
9
| class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size()+2,0);
for(int i=0;i<nums.size();i++)
dp[i+2]=max(dp[i+1],dp[i]+nums[i]);
return dp[nums.size()+1];
}
};
|
0-1背包 完全背包_哔哩哔哩_bilibili
二、01背包（模板，可以配合该视频和代码随想录博客一起看）
恰好装这个容量，求方案数量的最大最小价值和，那就是把选最大值的操作换成加号
494. 目标和 - 力扣（LeetCode）
后续如果做到了其他的变形题目会同步更新到这里
第一步：回溯法（深度优先遍历）
思路：
配合视频一起看更棒
0-1背包 完全背包_哔哩哔哩_bilibili
下面的就不画了，大家知道这个意思就行
选编号为i的话就是返回dfs(i-1,c-w[i])+v[i]，就是代表已经把编号为i的物品已经放入了背包（表现为容量减了w[i]，价值加了v[i]），然后继续递归下一个物品
不选编号为i的话就是返回dfs(i-1,c)，这个代表的是一共有i-1个物品，总共是c的容量，那背包能装的最大价值是多少
我们本层函数会产生两个递归，一个是选了i，一个是没选i，返回的都是对应情况的最大值，我们要选最大的，所以要在这两个里面再选一个更大的作为返回值返回
从而得出了递推公式。
这个虽然过不了，时间复杂度太高，但是这是学习动态规划的必由之路
1.返回值和参数
w各个物品所占空间
v各个物品价值
i遍历物品
c是当前剩余的容量
返回值返回选或不选编号为i的物品的最大值
1
| int dfs(vector<int>& w,vector<int>& v,int i,int c)
|
2.终止条件
1
2
3
4
| if(i<0)
return 0;
if(c<w[i])
return dfs(w,v,i-1,c);
|
如果编号小于0说明已经到了树形结构最下面了，要开始从第一个物品选了，即自底（第一个物品）向上（i依次增大）开始遍历
如果当前容量已经小于要选的物品，那就直接返回给上层不选i号物品的结果
3.本层逻辑
在选和不选当前物品两种情况中（只要返回回来的一定是最大值），挑一个更大的返回
1
| return max(dfs(w,v,i-1,c),dfs(w,v,i-1,c-w[i])+v[i]);
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int dfs(vector<int>& w,vector<int>& v,int i,int c)
{
if(i<0)
return 0;
if(c<w[i])
return dfs(w,v,i-1,c);
return max(dfs(w,v,i-1,c),dfs(w,v,i-1,c-w[i])+v[i]);
}
int 01knapsack(vector<int>& nums,int c) {
vector<int> w(nums.begin(),nums.end());
vector<int> v(nums.begin(),nums.end());
return dfs(w,v,nums.size()-1,c);
}
};
|
C++还可用lambda来写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int 01knapsack(vector<int>& nums,int c) {
vector<int> w(nums.begin(),nums.end());
vector<int> v(nums.begin(),nums.end());
function<int(int,int)> dfs=[&](int i,int c)->int{
if(i<0)
return 0;
if(c<w[i])
return dfs(i-1,c);
return max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]);
};
return dfs(nums.size()-1,c);
}
};
|
第二步：改成记忆化搜索
注意，在递归函数中，我们同时有物品编号i和容量c，所以要用一个二维数组作为哈希表来存储计算结果进行复用。
然后在每次返回结果前都赋值一下，把计算结果给存储起来
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int dfs(vector<int>& w,vector<int>& v,int i,int c,vector<vector<int>>& dp)
{
if(i<0)
return 0;
if(dp[i][c]!=-1)
return dp[i][c];
if(c<w[i])
return dp[i][c]=dfs(w,v,i-1,c,dp);
return dp[i][c]=max(dfs(w,v,i-1,c,dp),dfs(w,v,i-1,c-w[i],dp)+v[i]);
}
int 01knapsack(vector<int>& nums,int c) {
vector<int> w(nums.begin(),nums.end());
vector<int> v(nums.begin(),nums.end());
vector<vector<int>> dp(nums.size(),vector<int>(c+1,-1));
return dfs(w,v,nums.size()-1,c,dp);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int 01knapsack(vector<int>& nums,int c) {
vector<int> w(nums.begin(),nums.end());
vector<int> v(nums.begin(),nums.end());
vector<vector<int>> dp(nums.size(),vector<int>(c+1,-1));
function<int(int,int)> dfs=[&](int i,int c)->int{
if(i<0)
return 0;
if(dp[i][c]!=-1)
return dp[i][c];
if(c<w[i])
return dp[i][c]=dfs(i-1,c);
return dp[i][c]=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]);
};
return dfs(nums.size()-1,c);
}
};
|
第三步：一比一翻译成动态规划(递推)
1.确定dp数组以及下标的含义
二维数组，dp[i][c]就是第i个物品在容量为c时可以取到的最大价值
i是物品编号
c是当前背包的总容量
2.确定递推公式
对应回溯算法本层逻辑部分
选或者不选第i号物品，如果没选，那就和上一个物品第i-1件遍历到j时一样的价值，因为没有选第i号
如果选了那就是 第i-1件物品在j-w[i]时的价值+选择的第i件物品的价值v[i]
1
| dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
|
3.dp数组如何初始化
全都初始化为0
第一行在容量大于第一件物品所需容量的时候就当做把第一件给放了进行初始化
因为dp[0][i]的物品编号只有0，即第一件物品，所以只能选择第一件物品得到最大价值，不选的话价值就为0
1
2
3
| vector<vector<int>> dp(nums.size(),vector<int>(c+1,0));
for(int i=w[0];i<=c;i++)
dp[0][i]=v[0];
|
4.确定遍历顺序
从前往后遍历，先遍历物品或者先遍历容量都是可以的，因为先物品是按照行一行一行来遍历，递推公式中的两个值都可以在遍历得出来，按照容量一列一列遍历也同样可以得出来这两个值
但仅限于二维，如果是一维那就只能先遍历物品后遍历容量，而且只能从后往前遍历容量
因为递推公式中用到的两个值在一维中变成了这样：
1
2
3
4
| vector<int> dp(c+1,0);
for(int i=0;i<nums.size();i++)
for(int j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
|
第一行是刷新前的数组，第二行是要对第一行进行覆盖的值，通过第一行的dp[j]和dp[j-w[i]]这两个值进行更新
如果从前往后，那dp[j-w[i]]就会被覆盖，从而得到一个错误的答案
如果不太理解可以转至：代码随想录
0-1背包 完全背包_哔哩哔哩_bilibili视频里面也会讲到滚动数组相关
1
2
3
4
5
6
| for(int i=1;i<nums.size();i++)
for(int j=0;j<=c;j++)
if(j>w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int 01knapsack(vector<int>& nums,int c) {
vector<int> w(nums.begin(),nums.end());
vector<int> v(nums.begin(),nums.end());
vector<vector<int>> dp(nums.size(),vector<int>(c+1,0));
for(int i=w[0];i<=c;i++)
dp[0][i]=v[0];
for(int i=1;i<nums.size();i++)
for(int j=0;j<=c;j++)
if(j>w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
return dp[w.size()-1][c];
}
};
|
优化成一维数组：滚动数组
笔者就不误人子弟了，大家转至此链接代码随想录进行学习
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int 01knapsack(vector<int>& nums,int c) {
vector<int> w(nums.begin(),nums.end());
vector<int> v(nums.begin(),nums.end());
vector<int> dp(c+1,0);
for(int i=0;i<nums.size();i++)
for(int j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
return dp[c];
}
};
|
微信
支付宝
