本文主要是介绍代码随想录算法训练营第四十八天| km57. 爬楼梯、322. 零钱兑换、279.完全平方数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录算法训练营第四十八天
km57. 爬楼梯
题目链接:km57. 爬楼梯
- 确定dp数组以及下标的含义:j为背包的最大容量,dp[j]当容量为j有几种组合方式
- 确定递推公式:dp[j]=dp[j]+dp[j-i],不放当前数字组成目标值的种类+必须放当前数字组成 目标值的种类(为了保证一定放这个值,就要把需要的容量腾出来)
- dp数组如何初始化:容量为0,有一种放法,dp[0] = 1;
- 确定遍历顺序:先遍历物品,再遍历背包容量,求出来的是组合种类;先遍历背包容量再变量物品,求出来每个容量下不同物品排列的种类数。本题属于后者。
- 打印dp数组。
#include<iostream>
#include<vector>using namespace std;
int main(){int m,n;cin >> n >> m ;vector<int> dp(n + 1,0);dp[0] = 1;for(int j = 1;j <= n;j++){for(int i = 1;i <= m;i++){if(j >= i){dp[j]+=dp[j - i];}}}std::cout << dp[n] << std::endl;return 0;
}
322. 零钱兑换
题目链接:322. 零钱兑换
和 474.一和零一样,求组成背包重量值时元素的个数,不同的是本题求得是最少个数,474.一和零求的是最大个数。
- 确定dp数组以及下标的含义:dp[j]表示装满重量为j的背包,装满后的最小价值(每个硬币的价值为1,装满时少的硬币数等于最小价值)
- 确定递推公式:dp[j] = min(dp[j], dp[j - coins[i]] + 1);不换当前硬币的价值和换上当前硬币的价值中取最小。
- dp数组如何初始化:容量为0,价值为0。dp[0]=0。非0下标初始为int的最大值,保证装满时取最小值时能被替换。遍历结束没被替换证明无解返回负一。
- 确定遍历顺序:背包和物品先遍历拿个都行,本题对排列顺序无特殊要求。从小到大遍历,每个元素可以选取多次。
- 打印dp数组。
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {if (dp[j - coins[i]] != INT_MAX) {dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}if(dp[amount] == INT_MAX)return -1;return dp[amount];}
};
279.完全平方数
题目链接:279.完全平方数
提前准备完全平方数集合,作为物品。
- 确定dp数组以及下标的含义:dp[j]表示装满重量为j的背包,装满后的最小价值(每个数的价值为1,装满时少的数等于最小价值)
- 确定递推公式:dp[j] = min(dp[j], dp[j - num] + 1);不换当前完全平方数的价值和换上当前完全平方数的价值中取最小。
- dp数组如何初始化:容量为0,价值为0。dp[0]=0。非0下标初始为int的最大值,保证装满时取最小值时能被替换。
- 确定遍历顺序:背包和物品先遍历拿个都行,本题对排列顺序无特殊要求。从小到大遍历,每个元素可以选取多次。
- 打印dp数组。
class Solution {
public:int numSquares(int n) {vector<int> nums;for(int i = 1;i*i<=n;i++){nums.push_back(i*i);}vector<int>dp(n+1,INT_MAX);dp[0] = 0;for(int &num:nums){for(int j =num;j<=n;j++){if(dp[j-num]!=INT_MAX){dp[j] = min(dp[j],dp[j-num]+1);}}}return dp[n];}
};
这篇关于代码随想录算法训练营第四十八天| km57. 爬楼梯、322. 零钱兑换、279.完全平方数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!