主要內(nèi)容摘錄如下
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）硬霍。
機器人每次只能向下或者向右移動一步。機器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）扶踊。
問總共有多少條不同的路徑？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)馋没，非商業(yè)轉(zhuǎn)載請注明出處。
動態(tài)規(guī)劃總結(jié)：
DP是很典型的自下而上解決問題思路降传，能用DP解決的問題通常都具有重復(fù)子結(jié)構(gòu)或者重疊子問題篷朵，每第N狀態(tài)都由前N-1個特定狀態(tài)轉(zhuǎn)換而來。
那么問題來了婆排，如何思考DP問題呢声旺？萬一，一眼沒看出來怎么辦段只？
一般情況下腮猖，思考問題時候我們常常使用的是考慮起來更為簡單的自上而下分析（雖然我覺得我們的思維其實是既有上到下也有下到上），但是從結(jié)果逆推回起始點的時候是很容易歸納出題目規(guī)律的赞枕。
比如這道leetcode62缚够，對于最后一個Finish點幔妨，你可以知道能夠到達(dá)它和它自己沒關(guān)系，和它的上一步有關(guān)系谍椅，要么是從頭上那一格到達(dá)误堡，要么是從右邊那一格過來；
這樣就可以得到一個遞推式：dp[m][n]=dp[m-1][n]+dp[m][n-1];
得到遞推式后雏吭，再考慮從最開始問題往上演繹推理锁施，利用得到的遞推式，每一個子問題都是遵循著遞推式得到結(jié)果杖们，這樣由一個個重疊子問題就可以得到最后的答案悉抵。
AC代碼如下：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];//二維數(shù)組dp記錄走法類數(shù)
for(int i=0;i<n;i++) dp[0][i]=1;//任意一列第一行的走法只有一種,go down
//注意寫法，現(xiàn)在是確定行遍歷列 i<n,not i<m
for(int j=0;j<m;j++) dp[j][0]=1;//同理,go left
//完成遍歷行
for(int i=1;i<m;i++) //第二行開始
{
for(int j=1;j<n;j++)//第二列開始
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
//dp[i-1][j]:上一個 go down, dp[i][j-1]:上一個go left
}
}
return dp[m-1][n-1];
}}
還沒完摘完，最后有要注意的一個優(yōu)化問題姥饰，因為DP問題包含著很多的重疊子問題，計算過程必然有著重復(fù)的子計算孝治，因此遇到方便存儲子計算結(jié)果的問題列粪，可以通過減少存儲中間計算結(jié)果，對計算時間進(jìn)行優(yōu)化谈飒。
