70. 爬楼梯
思路：
这道题可以用完全背包的思路解答。步数为1和步数为2可以使用无数次，走n步可以看成背包的容量为n，题目可以转化成求解装满背包容量为n有多少种方法，注意这里的先走1步再走两步与先走两步再走一步是两种方法。dp[i]：背包容量为i有dp[i]种装法；递推关系：容量为i的背包可以由i-1的背包和i-2的背包装成的，所以dp[i]=dp[i-1]+dp[i-2]；初始化：dp[0]=1；遍历顺序：这里求得是排列，所以先遍历背包后遍历物品。
代码：
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+1,0);
int m=2;
dp[0]=1;
for(int j=0;j<=n;j++)
{
for(int i=1;i<=m;i++)
{
if(j>=i)dp[j]+=dp[j-i];
}
}
return dp[n];
}
};
322. 零钱兑换
思路：
因为钱币可以使用无数次，所以本题是完全背包类的问题。dp[i]：装满容量为i的背包需要的最少硬币个数为dp[i]；递推关系：dp[i]=min(dp[i-coins[i]]+1,dp[i]);初始值：dp[0]=0，因为递推关系里面取了min，所以其他的数值应该初始化为INT_MAX；遍历顺序：本题的问题是求解最少的硬币个数，不是求解实现最少硬币个数有多少种方法，所以本题按照排列或者组合方法求解都是可以的。
代码：
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-coins[i]]+1,dp[j]);
}
}
}
if(dp[amount]==INT_MAX) return -1;
else return dp[amount];
}
};
279. 完全平方数
思路：
本题也可看成是一个完全背包问题，相同的完全平方和数可以取到多次。dp[i]：组成和为i的最少完全平方数的数量；递推关系：dp[j]=min(dp[j-i*i]+1,dp[j])；初始值：dp[0]=0，其他值为INT_MAX；遍历顺序：先背包后物品或者先物品后背包均可。 这道题的整体思路和上面一道题是一致的。
代码：
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;j++)
{
if(dp[j-i*i]!=INT_MAX)
{
dp[j]=min(dp[j-i*i]+1,dp[j]);
}
}
}
return dp[n];
}
};
