動(dòng)態(tài)規(guī)劃是一種算法套路，通常用來求一些最優(yōu)解什么的，它的最精髓的地方個(gè)人認(rèn)為就是它是反過來推理的，有一些題目按照腦子別的正常思路來思考往往會(huì)很亂。

舉個(gè)例子來說；

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法

正常來思考：
跳一級(jí)臺(tái)階n = 1：就只有一種方式
跳兩級(jí)臺(tái)階n = 2：兩種方式：1+1；2；
跳三級(jí)臺(tái)階n = 3：三種方式：1+1+1；1+2；2+1；
跳四級(jí)臺(tái)階n = 4：五種方式：1+1+2；2+2；1+1+1+1；1+2+1；2+1+1；
。。。。。

像這樣越往后越復(fù)雜，想著想著就亂了，感覺就像在腦子里面有棵樹，然后不斷的分叉，約分越多，根本理不清。

動(dòng)態(tài)規(guī)劃就是要倒過來思考，知識(shí)點(diǎn)啊：：：：

比如n=10，到達(dá)10級(jí)臺(tái)階只有兩種方式：從第9級(jí)跨一步過來，或者從第8級(jí)跨兩級(jí)過來。

那么我只要知道到達(dá)第9級(jí)的方式數(shù)+到達(dá)第8級(jí)的方式數(shù)就可以了。至于第9級(jí)和第8級(jí)的方式數(shù)到底是多少。那是它們自己的事，不是我第10級(jí)該管的。

以同樣的方式，一直往前推，到第一級(jí)和第二級(jí)，n = 1和n = 2的情況是已知的。

public class Solution {
    public int JumpFloor(int target) {
        //dp數(shù)組存放到達(dá)每一級(jí)臺(tái)階可以有的方式數(shù)
        int dp[] = new int[target+1];
        for (int i = 0; i < dp.length; i++) {
            if (i==0){
                //0級(jí)臺(tái)階0種方式
                dp[i]=0;
            }else if (i==1){
                //1級(jí)臺(tái)階1種方式
                dp[i]=1;
            }else if (i==2){
                //2級(jí)臺(tái)階2種方式
                dp[i]=2;
            }else {
                //其他臺(tái)階都是從上一級(jí)臺(tái)階跨一步上來，或者上兩級(jí)臺(tái)階跳2級(jí)上來
                dp[i] = dp[i-1]+dp[i-2]; 
            }
            
        }
        return dp[target];
    }
}

這種動(dòng)態(tài)規(guī)劃的重點(diǎn)在與從題目的一次可以跳一級(jí)或者兩級(jí)臺(tái)階找到dp[i] = dp[i-1]+dp[i-2]這層關(guān)系，然后再找到特例的幾個(gè)值就是n=1和n=2的情況。

然后再看一個(gè)例子：

1,3,5,9
8,1,3,4
5,0,6,1
8,8,4,0
這是一個(gè)二維數(shù)組，從左上角開始每次只能向右走或者向下走，最后達(dá)到右下角的位置，路徑中所有數(shù)字累加起來就是路徑和，返回所有路徑的最小路徑和。

從1開始走，到達(dá)0，有很多岔道，并且難以確定哪條路比較近，要把所有路徑都列出來一個(gè)個(gè)求根本不靠譜。
按照動(dòng)態(tài)規(guī)劃倒著思考的思路，在本題中要根據(jù)“每次只能向右走或者向下走”推理出到達(dá)最后的0有兩種：從1往下走，或者從4往右走，也就是說只要比較一下到達(dá)4的最短路徑和+0和到達(dá)1的最短路徑和+0誰比較小即可。
繼續(xù)推理，到達(dá)4也有兩種：從8往右走，或者從6往下走，比較一下到達(dá)8的最短路徑和+4和到達(dá)6的最短路徑和+4誰比較小即可。

其中第0行和第0列都是特殊的，最好拿出來特殊處理。

import java.util.ArrayList;
public class Solution {
    public int test(int [][] array) {
        int row = 0;
        int col = 0;
        //存放到達(dá)每個(gè)位置的最短路徑和。
        int dp[][] = new int[array.length][array[0].length];
        //遍歷二維數(shù)組，給dp賦初值。（用兩個(gè)for遍歷也是一樣的）
        while(row<array.length){
            dp[row][col] = 9999;
            col++;
            if (col == array[row].length){
                row++;
                col = 0;
            }
        }
        
        
         row = 0;
         col = 0;
         
         //遍歷數(shù)組，計(jì)算每個(gè)值的最短路徑和放入dp數(shù)組中
        while(row<array.length){
            if (row == 0 && col == 0){
                //第一個(gè)就是它本身
                dp[row][col] = array[row][col];
            }else if (row == 0){
                //第一行的只能從它左邊走過來
                dp[row][col] = array[row][col] + dp[row][col - 1];
            }else if (col == 0){
                //第一列的只能從它上邊走過來
                dp[row][col] = array[row][col] + dp[row - 1][col];
            }else {
                //從左邊或者上邊過來，選擇小的一個(gè)。
                dp[row][col] = array[row][col] + Math.min(dp[row-1][col], dp[row][col - 1]);
            }
            col++;
            if (col == array[row].length){
                row++;
                col = 0;
            }
        }
        
        //打印dp數(shù)組
        for (int[] is : dp) {
            for (int i : is) {
                System.out.print(i+" ");
            }
            System.out.println(" ");
        }

        return dp[dp.length-1][dp[0].length-1];
    }
}