动态规划part07 70.爬楼梯（进阶） 322. 零钱兑换 279. 完全平方数
70.爬楼梯（进阶）（题目链接点我）
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> dp(n+1); //dp[i]表示爬到第i层楼梯有dp[i]种方法
dp[0] = 1; //0的时候有一种方法
for(int j = 1; j<n+1;j++){ //排列问题，先遍历背包
for(int i=1 ;i<=m;i++){
if(j-i>=0) dp[j] += dp[j-i];
}
}
std::cout << dp[n] << std::endl;
return 0;
}
322. 零钱兑换
动规五部曲：
1.确定dp数组以及下标的含义
dp[j]含义是，装满容量为j的背包，所需的最少硬币个数
2.确定递推公式
dp[j] = min(dp[j], dp[j-coins[i]] + 1);
3.dp数组如何初始化
dp[0] = 0;
for(int i = 1;i<dp.size();i++) dp[i] = INT_MAX;
4.确定遍历顺序
组合数排列数无所谓，可以是先物品再背包，或者先背包再物品
5.举例推导dp数组
以输入：coins = [1, 2, 5], amount = 5为例
dp[amount]为最终结果。
方法一：先物品后背包
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< dp.size();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];
}
};
方法二：先背包后物品
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;
for(int j = 0; j<=amount;j++){
for(int i = 0; i<coins.size();i++){
if(j-coins[i]>=0 && 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. 完全平方数
和322. 零钱兑换非常类似，直接上代码
方法一：先物品后背包
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
for(int i = 0; i*i<=n;i++){
for(int j = i*i; j<n+1;j++){
if(dp[j-i*i]!=INT_MAX) dp[j] = min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
};
方法二：先背包后物品
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
for(int j = 0; j<n+1;j++){
for(int i =1; i*i<=j;i++){
dp[j] = min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
};
