【C++编程能力提升】

一、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];
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、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];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、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];
    }
1
2
3
4
5
6
7
8
9
10
11