代码随想Day45 | 70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数

这道题用完全背包的思路来做就是一个排列数，先背包在物品。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];

    }
};