DAY45 70. 爬楼梯 + 322. 零钱兑换 + 279.完全平方数

零钱兑换 + 279.完全平方数"/>

DAY45 70. 爬楼梯 + 322. 零钱兑换 + 279.完全平方数

70. 爬楼梯

题目要求：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

爬楼梯的dp版本，完全背包。

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+1, 0);dp[0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= 2; ++j) {if (i - j >= 0) dp[i] += dp[i-j];}}return dp[n];}
};

• 时间复杂度: O(nm)
• 空间复杂度: O(n)

322. 零钱兑换

题目要求：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

思路

amount是背包，coins数组是物品。但是求的是组成amount的最少硬币个数，而不是能组成amount的总数。因此dp[i]表示的是组成i需要用到的最少硬币个数，如果硬币不能组成i则赋值为-1。

否则dp[i] = min(dp[i], dp[i-j] + 1);

初始条件dp[0] = 0; 组成amount=0的最少硬币数是0，和之前的初始条件也不太一样。

遍历顺序按照完全背包的遍历顺序，外层amount，内层coins。

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]] != -1) {dp[i] = min(dp[i], dp[i - coins[j]] + 1);}}// cout << dp[i] << endl;if (dp[i] == INT_MAX) dp[i] = -1;}return dp[amount];}
};

279.完全平方数

题目要求：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路

和上一个题目类似，只不过coins换成了小于n的完全平方数序列，amount换成了n。

额外做一个小于n的完全平方数列就可以了。

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1, INT_MAX);vector<int> item;for (int i = 1; i * i <= n; ++i) {item.push_back(i * i);}dp[0] = 0;for (int i = 0; i <= n; ++i) {for (int j = 0; j < item.size(); ++j) {if (i >= item[j] && dp[i - item[j]] != -1) {dp[i] = min(dp[i], dp[i - item[j]] + 1);}}if (dp[i] == INT_MAX) dp[i] = -1;}return dp[n];}
};

• 时间复杂度: O(n * √n)
• 空间复杂度: O(n)

总结：今天的题目有点简单，是完全背包的应用，思路完全类似，注意初始条件、循环顺序、循环中的dp数组更新以及一些必要的条件判断即可。