322. 零錢兌換
給你一個整數數組 coins 凉夯，表示不同面額的硬幣杜顺；以及一個整數 amount ，表示總金額个束。
計算并返回可以湊成總金額所需的 最少的硬幣個數 慕购。如果沒有任何一種硬幣組合能組成總金額，返回 -1 茬底。
你可以認為每種硬幣的數量是無限的沪悲。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coin-change
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權桩警，非商業(yè)轉載請注明出處可训。
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
// 填充dp
Arrays.fill(dp, amount + 1);
dp[0] = 0;
// 求0-amount每個的可取個數
for (int i = 0; i <= amount; i++) {
// 每一個金額的最小個數
for (int n : coins) {
// 無可取硬幣
if (i - n < 0) continue;
dp[i] = Math.min(dp[i], 1 + dp[i - n]);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
結果如下：
70. 爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂捶枢。
每次你可以爬 1 或 2 個臺階握截。你有多少種不同的方法可以爬到樓頂呢？
示例 1：
輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂烂叔。
- 1 階 + 1 階
- 2 階
示例 2：
輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂谨胞。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/climbing-stairs
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權蒜鸡，非商業(yè)轉載請注明出處胯努。
class Solution {
public int climbStairs(int n) {
if (n == 1) return 1;
// 記錄爬樓梯次數
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
int pre = dp[1], cur = dp[2];
for (int i = 3; i <= n; i++) {
dp[i] = pre + cur;
pre = cur;
cur = dp[i];
}
return dp[n];
}
}
結果如下：
