70. 爬楼梯 （进阶）
这道题用完全背包的思路来做就是一个排列数，先背包在物品。dp[i]是爬到第i个台阶最多的方法数。递推公式：dp[i]+=dp[i-j]；初始化dp[0]=1，因为dp[0]是整个递推的基础。
详细代码如下：
#include<iostream>
#include<vector>
using namespace std;
void climbStaircase(int n,int 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];
}
}
cout<<dp[n];
}
int main()
{
int n,m;
cin>>n>>m;
climbStaircase(n,m);
return 0;
}322. 零钱兑换
dp[i]是容量为i的背包的最小物品数，dp[i]=min(dp[i-coin[j]]+1,dp[i])。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
但是最小个数和顺序无关，因此那种遍历顺序都可以。
详细代码如下：这道题使用先背包后物品
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,INT_MAX);
dp[0]=0;
for(int i=1;i<=amount;i++)
{
for(int j=0;j<coins.size();j++)
{
if(i>=coins[j]&&dp[i-coins[j]]!=INT_MAX)
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
}
if(dp[amount]==INT_MAX) return -1;
return dp[amount];
}
};279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，要注意这里等比于上述题目的coin数组里的值是i*i(1,4,9,16...)，明白这一点就能推出这道题的思路，注意这道题不存在凑不成的情况，因为完全平方数里有1这一项。
使用先物品后背包的思路详细代码：
class Solution {
public:
int numSquares(int n) {
//先物品再背包
vector<int>dp(n+1,INT_MAX);
dp[0]=0;
for(int i=1;i*i<=n;i++) //物品
{
for(int j=i*i;j<=n;j++) //背包
{
dp[j]=min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
};
