【Day50】代码随想录之动态规划完全背包_70. 爬楼梯进阶_322. 零钱兑换 _279.完全平方数
动态规划理论基础
动规五部曲:
- 确定dp数组 下标及dp[i] 的含义。
- 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
- 初始化dp数组。
- 确定遍历顺序:从前到后or其他。
- 打印。
出现结果不正确:
- 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。
- 打印dp日志和自己想的不一样:代码实现细节出现问题。
70. 爬楼梯进阶
参考文档:代码随想录
分析:
根据题目描述是完全背包的排列问题,遍历顺序为先背包再物品。
dp五部曲:
- dp[i]含义:爬到j楼的方法个数。
- 递推公式:dp[i] += dp[i-j];
- 初始化:dp[0] = 1, 其余位置为0。
- 遍历顺序:先背包再物品。
代码:
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int main(){
int m = 0, n = 0;
scanf("%d%d",&n, &m);
vector<int> dp(n+1, 0);
dp[0] = 1;
for(int i = 1; i <= n; i++){//先背包
for(int j = 1; j <= m; j++){//再物品
if(i >= j) dp[i] += dp[i-j];
}
}
printf("%d", dp[n]);
return 0;
}
322. 零钱兑换
参考文档:代码随想录
分析:
dp公式:dp[j] = min(dp[j], dp[j-coins[i]]+1)。
因为题目求的是最少的硬币个数,所以排列组合都可以,即物品和背包的遍历顺序均可。
初始化需要注意dp[0]是0,其余的为了不影响之后的取最小值,定义为32位数的最大值INT_MAX。
代码:
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//dp[j]:amount=j需要的最少硬币个数
//dp[j] = min(dp[j], dp[j-coins[i]]+1);
//dp[0] = 0, 其他初始化INT_MAX
vector<double> dp(amount+1, INT_MAX);
dp[0] = 0;
for(int i = 0; i < coins.size(); i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] = min(dp[j], dp[j-coins[i]]+1);
}
}
if(dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};
279.完全平方数
参考文档:代码随想录
分析:
dp公式改变:dp[j] = min(dp[j], dp[j-i*i]+1);
代码:
class Solution {
public:
int numSquares(int n) {
//dp[j]: 和为j的完全平方数的最少数量
//dp[j] = min(dp[j], dp[j-i*i]+1);
//初始化:dp[0] = 0,其余初始化是INT_MAX
int nums = n/2;
if(n == 1) nums = 1;
vector<double> dp(n+1, INT_MAX);
dp[0] = 0;
for(int i = 1; i <= nums; i++){
for(int j = i*i; j <= n; j++){
dp[j] = min(dp[j], dp[j-i*i]+1);
}
}
return dp[n];
}
};
原文地址:https://blog.csdn.net/weixin_46275441/article/details/136152813
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!