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

舉個(gè)例子來(lái)說(shuō)庙曙；

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

正常來(lá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ù)雜桅锄，想著想著就亂了琉雳，感覺(jué)就像在腦子里面有棵樹(shù)，然后不斷的分叉友瘤，約分越多翠肘，根本理不清。

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

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

那么我只要知道到達(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)階跨一步上來(lái)律歼，或者上兩級(jí)臺(tái)階跳2級(jí)上來(lái)
                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ù)組苗膝，從左上角開(kāi)始每次只能向右走或者向下走，最后達(dá)到右下角的位置植旧，路徑中所有數(shù)字累加起來(lái)就是路徑和辱揭，返回所有路徑的最小路徑和。

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

其中第0行和第0列都是特殊的又厉，最好拿出來(lái)特殊處理九府。

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){
                //第一行的只能從它左邊走過(guò)來(lái)
                dp[row][col] = array[row][col] + dp[row][col - 1];
            }else if (col == 0){
                //第一列的只能從它上邊走過(guò)來(lái)
                dp[row][col] = array[row][col] + dp[row - 1][col];
            }else {
                //從左邊或者上邊過(guò)來(lái)煌妈，選擇小的一個(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];
    }
}