動態(tài)規(guī)劃思想：
有規(guī)律的迭代，當前迭代的結果與上一次的結果有關。
一般套路：根據(jù)已知條件推算出規(guī)律， 將每次迭代的結果記錄下來。（可以新建dp數(shù)組記錄）
1. 爬樓梯：
假設樓梯為3： 有兩種可能性，
? ? ? ? ? ? ? ? ? ? ? ? ?1. 目前站在第一階，然后邁兩步上第二階： 1+2
2. 目前站在第二階，邁一步： 2+1
? ? 假設現(xiàn)在站在第二節(jié)，到第二節(jié)的方法
2.1 邁一步到第二節(jié)： 2
2.2 邁一步到第一節(jié)，再邁一步到第二節(jié)
3. 所以到第二節(jié)的方法有三種，1+2， 2+1， 1+1? +1；
4. 方法抽象：若n>=3, 則其到達的方法可以分解為上一階到達的路徑個數(shù)加上兩節(jié)到達的路徑個數(shù)。?
class Solution {
public int climbStairs(int n) {
? ? //若樓梯數(shù)小于等于1，不需要帶入通事，直接返回n值即為答案
? ? if(n <= 1){
? ? ? ? return n;
? ? }
? ? //新建dp數(shù)據(jù)記錄每一次迭代路徑。 為了簡化理解，我們一般求的答案為dp【n】的值。所以需要新建大小為n+1的數(shù)據(jù)
? ? int[] dp = new int[n+1];
? ? //通式中，第一節(jié)的方法為1
? ? dp[1] = 1;
? ? //通式中，第二節(jié)的方法為2
? ? dp[2] = 2;
? ? //通式中，第三節(jié)以上為前兩節(jié)和前一階之和
? ? for(int i = 3; i < n+1; i++){
? ? ? ? dp[i] = dp[i-1] + dp[i-2];
? ? }
? ? //返回第n階的值為答案
? ? return dp[n];
}
}
2. 找零錢
和上一題爬樓梯類似，只不過爬樓梯是找出全部可能路徑，找零錢為找出最少次數(shù)。 可以先采用自底向上分析
1. 找一元的最少次數(shù)： 1---》1次
2. 找二元的最少次數(shù)：2---》1次
3. 找3元的最少次數(shù)：3 = 2+1；----》2次
?3.1 先找2元
3.2 再找1 元
4. 找4元的最少次數(shù)： 4 = 2 + 2 ----》2次
5. 找5元的最少次數(shù)： 1 次
6. 找6 元： 6 = 5 + 1---》2
7. 7 = 5 +2---》2
8. 8 = 5 + 3 ----> 1次加上兩次--》3
9. 9 = 5 + 4 ----》 1 + 2---》3
10. 10 = 5 + 5 ----》2
11. 11 = 10 + 1--->2+1---》3
由上可以看出，我們再后面的迭代中，我們可以使用前面的結果簡化計算
class Solution {
public int coinChange(int[] coins, int amount) {
? ? //初始化dp數(shù)據(jù)
? ? int[] dp = new int[amount+1];
? ? //填充dp數(shù)據(jù)，保證每一個值都大于amount，以便以后得出最小次數(shù)
? ? Arrays.fill(dp, amount+1);
? ? //當amount為0時，次數(shù)為0；
? ? dp[0] = 0;
? ? //從總錢為0時開始遍歷求出每一錢所對應的值
? ? for(int i = 0; i < amount+1; i++){
? ? ? ? //遍歷零錢
? ? ? ? for(int j = 0; j < coins.length; j++){
? ? ? ? ? ? //若零錢數(shù)小于等于當前總錢數(shù)時
? ? ? ? ? ? if(coins[j] <= i){
? ? ? ? ? ? ? ? //判斷當前錢數(shù)的找錢次數(shù)，和找過錢數(shù)中的相關值+1
? ? ? ? ? ? ? ? dp[i] = Math.min(dp[i], (dp[i-coins[j]]+1));
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? //若沒有找到對應的零錢數(shù)，則dp中的值不發(fā)生更改，還為最大值。
? ? //若為最大值則返回-1， 若不是，則返回當前所儲存的值。
? ? return dp[amount] > amount? -1: dp[amount];
}
}
