70. 爬楼梯 （进阶）
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
int[] weight = {1,2};
dp[0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < weight.length; j++) {
if (i >= weight[j]) dp[i] += dp[i - weight[j]];
}
}
return dp[n];
}
}
322. 零钱兑换
这道题自己没做出来，但是思路理解了。
因为是并不是每个零钱只能用一次，所以遍历零钱的循环放在里外都可以。
这道题有几个难点要想通：
- 为什么取dp[i - coins[j]] + 1和 dp[i] 的最小值。取dp[i]的最小值好理解，dp[i - coins[j]] + 1的意思是当前如果amount是7，coin遍历到了5，那么能凑成的组合数就是 如果amount是2时候也凑成了组合数，那么目前的coin到了5 也就是在2的组合数基础上加上coin5，所以就是加了一个币，那就是+1。(要强调的是dp的含义是最少多少个币凑成当前需要的数)
- 要把dp数组的数初始化为INT_MAX，也就是最大值。这样的话才可以比较min。如果都初始化为0的话，那么比较每个数的最小值的时候就没有效果了。另外也要保证遍历的时候，dp[i - coins[j]] 也要不能是INT_MAX，因为如果结果是INT_MAX，那说明dp[i - coins[j]]没能凑出个组合来。
- 最后的dp[amount]如果是初始值，也就是INT_MAX，说明就是没找到任何一个coin的组合来凑成所需的amount。
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(coins[j] <= i && dp[i - coins[j]] != INT_MAX){ dp[i] = min(dp[i - coins[j]] + 1, dp[i]); } } } if (dp[amount] == INT_MAX) return -1; return dp[amount]; } };
279.完全平方数
思路是理解了，但是自己还是写不出来。想不出来递推公式。
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for(int i=0; i<=n; i++){
for(int j=1; j*j<=i; j++){
if(dp[i-j] != INT_MAX)
dp[i] = min(dp[i],dp[i - j * j] + 1);
}
}
return dp[n];
}
};
