【C++编程能力提升】-CSDN博客

一、70 爬楼梯

题目链接70 爬楼梯

核心背包容量是爬到楼顶的阶数n物品是每次爬楼梯的数量1或2.
由于先爬1阶再爬2阶和先爬2阶再爬1阶是不同的组合方法因此本题是排列问题需要先遍历背包容量再遍历物品。

    int climbStairs(int n) {
        //完全背包问题背包容量是n物品是1或2,且是排列问题不是组合
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int j=0;j<=n;j++)
        {//排列问题先遍历背包容量再遍历物品
            for(int i=1;i<=2;i++)
            {//物品就是每次爬台阶的个数
                if(j>=i)
                    dp[j]+=dp[j-i];
            }
        }
        return dp[n];
        }

二、322 零钱兑换

题目链接322 零钱兑换

核心背包容量是amount物品是coins数组的硬币且求解组合的最小数量因此本题无需关注遍历顺序。
第一求解最小值故初始化为INT_MAX避免初始化为0时无法被覆盖
第二dp[0]=0这是非常重要的即凑成0的方法有0种
第三如果dp[j-coin[i]]==INT_MAX则无需更新此时保持dp[j]=dp[j]即可。

    int coinChange(vector<int>& coins, int amount) {
    //完全背包问题背包容量是amount求解装满背包的不同组合数且最小重点是最小而不是顺序
        vector<int> dp(amount+1,INT_MAX);    //求解最小值故初始化为max
        dp[0]=0;    //凑成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) //max无需更新
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
        }
        if(dp[amount]==INT_MAX)
            return -1;  //需要check最后一个元素是否仍为max
        return dp[amount];
    }

三、279 完全平方数

题目链接279 完全平方数

核心背包容量是整数n物品是1-n之间的所有完全平方数。求解最少数量说明遍历顺序是没有要求的遍历的物品是从1开始到iI(ii<=n)。

    int numSquares(int n) {
        //完全背包问题背包容量是n物品是1-n的所有完全平方数
        vector<int> dp(n+1,INT_MAX);    //求解最少数量初始化需为max
        dp[0]=0;    //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];
    }