前言

摘自：代碼隨想錄

動(dòng)態(tài)規(guī)劃五部曲：

1. 確定dp數(shù)組（dp table）及其下標(biāo)的含義
2. 確定遞推公式
3. 初始化dp數(shù)組
4. 確定遍歷順序
5. 舉例推導(dǎo)dp數(shù)組

1 最少硬幣數(shù)

leetcode 322. 零錢兌換

動(dòng)規(guī)五部曲分析如下：

1. 確定dp數(shù)組以及下標(biāo)的含義

dp[j]：湊足總額為 j 所需錢幣的最少個(gè)數(shù)為dp[j]

2. 確定遞推公式

湊足總額為j - coins[i]的最少個(gè)數(shù)為dp[j - coins[i]]，

那么只需要加上一個(gè)錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]（考慮coins[i]）

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3. dp數(shù)組如何初始化

首先湊足總金額為0所需錢幣的個(gè)數(shù)一定是0，那么dp[0] = 0;

其他下標(biāo)對(duì)應(yīng)的數(shù)值呢？

考慮到遞推公式的特性，dp[j]必須初始化為一個(gè)最大的數(shù)，否則就會(huì)在min(dp[j - coins[i]] + 1, dp[j])比較的過(guò)程中被初始值覆蓋。

所以下標(biāo)非0的元素都是應(yīng)該是最大值。

int[] dp = new int[amount + 1];
// 往數(shù)組dp里面填充某個(gè)數(shù)，這里選擇amount+1，就是最大的值
Arrays.fill(dp, amount+1);
dp[0] = 0;

4. 確定遍歷順序

有兩種方式：

第一種：外循環(huán)遍歷金額，內(nèi)循環(huán)遍歷硬幣面額。

第二種：外循環(huán)遍歷硬幣面面額，內(nèi)循環(huán)遍歷金額。

這兩種遍歷順序?qū)?yīng)的意義如下：

1. 外循環(huán)遍歷金額，內(nèi)循環(huán)遍歷硬幣面額：

   這種遍歷順序的意義是在計(jì)算找零過(guò)程中，我們首先考慮金額的變化，然后再考慮不同的硬幣面額。

   也就是說(shuō)，我們固定一個(gè)金額，嘗試使用不同的硬幣面額來(lái)找零。這樣做的好處是可以利用之前已經(jīng)計(jì)算出來(lái)的金額的最少硬幣數(shù)，快速得到當(dāng)前金額的最優(yōu)解。由于金額是從小到大遞增的，所以我們?cè)谟?jì)算每個(gè)金額的最優(yōu)解時(shí)，可以利用前面較小金額的最優(yōu)解已經(jīng)被計(jì)算出來(lái)的特點(diǎn)。

// 遍歷金額
for (int i = 1; i <= amount; i++) {// 遍歷硬幣面額for (int j = 0; j < coins.length; j++) {if (coins[j] <= i) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}
}

2. 外循環(huán)遍歷硬幣面額，內(nèi)循環(huán)遍歷金額：

   這種遍歷順序的意義是在計(jì)算找零過(guò)程中，我們首先考慮不同的硬幣面額，然后再考慮不同的金額。

   也就是說(shuō)，我們固定一個(gè)硬幣面額，嘗試在不同的金額下進(jìn)行找零。這樣做的好處是可以保證我們將所有可能的硬幣面額都考慮到，并且在計(jì)算每個(gè)金額的最優(yōu)解時(shí)，可以利用之前已經(jīng)計(jì)算出來(lái)的較小金額的最優(yōu)解。由于硬幣面額是從小到大遞增的，所以我們?cè)谟?jì)算每個(gè)金額的最優(yōu)解時(shí)，可以利用之前較小硬幣面額的最優(yōu)解已經(jīng)被計(jì)算出來(lái)的特點(diǎn)。

// 遍歷硬幣面額
for (int coin : coins){// 遍歷金額for (int i = 1; i <= amount; i++) {if(coin <= i){dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}
}

全部代碼如下：

第一種：

class Solution {public int coinChange(int[] coins, int amount) {// 初始化dp數(shù)組int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;// 遍歷金額for (int i=1; i <= amount; i++) {// 遍歷硬幣面額for (int j=0; j < coins.length; j++){if(coins[j] <= i){dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}

第二種：

class Solution {public int coinChange(int[] coins, int amount) {// 初始化dp數(shù)組int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;// 遍歷硬幣面額for (int coin : coins){// 遍歷金額for (int i = 1; i <= amount; i++) {if(coin <= i){dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}

2 最長(zhǎng)連續(xù)遞增子序列

leetcode 674. 最長(zhǎng)連續(xù)遞增序列

動(dòng)規(guī)五部曲分析如下：

1. 確定dp數(shù)組以及下標(biāo)的含義

dp數(shù)組：表示以當(dāng)前元素為結(jié)尾的最長(zhǎng)連續(xù)遞增序列的長(zhǎng)度。

dp[i]表示以nums[i]為結(jié)尾的最長(zhǎng)連續(xù)遞增序列的長(zhǎng)度。

2. 確定遞推公式

如果nums[i] > nums[i-1]，則dp[i] = dp[i-1] + 1；否則dp[i] = 1。

3. dp數(shù)組如何初始化

我們將dp數(shù)組的所有元素初始化為1，因?yàn)槊總€(gè)元素都可以作為一個(gè)單獨(dú)的遞增序列。

4. 確定遍歷順序

從第二個(gè)元素開(kāi)始遍歷：

for(int i=0; i < nums.length; i++){if(i > 0 && nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}
}

5. 舉例說(shuō)明

舉例說(shuō)明：給定數(shù)組nums = [1, 3, 5, 4, 7]。

遍歷過(guò)程如下：

• 對(duì)于nums[1] = 3，nums[0] = 1 < nums[1]，所以dp[1] = dp[0] + 1 = 2。
• 對(duì)于nums[2] = 5，nums[1] = 3 < nums[2]，所以dp[2] = dp[1] + 1 = 3。
• 對(duì)于nums[3] = 4，nums[2] = 5 > nums[3]，所以dp[3] = 1。
• 對(duì)于nums[4] = 7，nums[3] = 4 < nums[4]，所以dp[4] = dp[3] + 1 = 2。

最終的最長(zhǎng)連續(xù)遞增序列的長(zhǎng)度為dp數(shù)組的最大值，即為3。

最后代碼如下：

class Solution {public int findLengthOfLCIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int[] dp = new int[nums.length];dp[0] = 1;for(int i=1; i < nums.length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}}return Arrays.stream(dp).max().getAsInt();}
}

不是使用stream的方式：

class Solution {public int findLengthOfLCIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int[] dp = new int[nums.length];dp[0] = 1;int maxLength = 1;for(int i=1; i < nums.length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}maxLength = Math.max(maxLength, dp[i]);}return maxLength;}
}

還可以得到dp[i]，再遍歷一遍得到最大值，這就不寫了

3 最長(zhǎng)遞增子序列

leetcode 300. 最長(zhǎng)遞增子序列

1. 確定dp數(shù)組（dp table）及其下標(biāo)的含義：

   • dp數(shù)組：dp[i] 表示以第i個(gè)數(shù)字結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。
   • 下標(biāo)的含義：dp[i] 表示以第i個(gè)數(shù)字結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。

2. 確定遞推公式：

   • 如果nums[i] > nums[j]，則：dp[i] = max(dp[i], dp[j] + 1)。

   為啥呢？？

   這里的i和j表示數(shù)組nums的索引。具體來(lái)說(shuō)，i表示當(dāng)前遍歷到的元素的索引，而j表示在i之前的元素的索引。

   當(dāng)我們遍歷到第i個(gè)元素時(shí)，我們需要尋找在i之前的元素中比nums[i]小的元素。這樣，我們就可以利用這個(gè)小于nums[i]的元素來(lái)構(gòu)成一個(gè)更長(zhǎng)的遞增子序列。

   所以，當(dāng)nums[i] > nums[j]時(shí)，表示nums[i]比nums[j]大，我們可以將以j結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度加1，然后與以i結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度進(jìn)行比較，取較大的值作為以i結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。也就是遞推公式中的 dp[i] = max(dp[i], dp[j] + 1)。

3. 初始化dp數(shù)組：

   • 初始時(shí)，dp數(shù)組中的每個(gè)元素都設(shè)為1，因?yàn)樽疃痰倪f增子序列長(zhǎng)度為1。

4. 確定遍歷順序：

   • 外層循環(huán)遍歷數(shù)組nums，從左到右依次計(jì)算dp[i]的值。
   • 內(nèi)層循環(huán)遍歷數(shù)組nums，從數(shù)組開(kāi)始到i的位置，尋找前面的數(shù)字nums[j]是否小于nums[i]，如果是，則根據(jù)遞推公式更新dp[i]的值。

5. 舉例推導(dǎo)dp數(shù)組：

   如果nums[i] > nums[j]，則dp[i] = max(dp[i], dp[j] + 1)。

   逐個(gè)元素計(jì)算dp[i]的值：

   • 當(dāng)i = 1時(shí)，nums[i] = 9，此時(shí)沒(méi)有比9小的元素，所以以9結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度仍為1。

   nums: 10 9 2 5 3 7 101 18
   dp: 1 1 1 1 1 1 1 1

   • 當(dāng)i = 2時(shí)，nums[i] = 2，此時(shí)在2之前有9和10兩個(gè)元素，都比2大，所以以2結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度仍為1。

   nums: 10 9 2 5 3 7 101 18
   dp: 1 1 1 1 1 1 1 1

   • 當(dāng)i = 3時(shí)，nums[i] = 5，此時(shí)在5之前有2和9兩個(gè)元素，其中2比5小，所以以5結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度為dp[2] + 1 = 2。

   nums: 10 9 2 5 3 7 101 18
   dp: 1 1 1 2 1 1 1 1

   • 當(dāng)i = 4時(shí)，nums[i] = 3，此時(shí)在3之前有2和5兩個(gè)元素，其中2比3小，所以以3結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度為dp[2] + 1 = 2。

   nums: 10 9 2 5 3 7 101 18
   dp: 1 1 1 2 2 1 1 1

后面略~~~~~~

完整代碼如下：

class Solution {public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n];dp[0] = 1; int result = 1; for (int i = 1; i < n; i++) {dp[i] = 1; for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); }}result = Math.max(result, dp[i]); }return result;}
}

4 完全平方數(shù)

leetcode 279. 完全平方數(shù)

動(dòng)態(tài)規(guī)劃五部曲：

1. 確定dp數(shù)組（dp table）及其下標(biāo)的含義

**dp[i]：**表示數(shù)字i的最少完全平方數(shù)的個(gè)數(shù)。

2. 確定遞推公式

對(duì)于數(shù)字 i 來(lái)說(shuō)，我們需要遍歷所有小于等于 i 的完全平方數(shù) j（ j 從 1 到 sqrt(i) ），然后將當(dāng)前數(shù)字 i 減去 j 得到差值，即 i - j 。我們需要找到 dp[ i - j * j ] 的最小值，然后再加上1（表示當(dāng)前完全平方數(shù) j ），即可得到dp[i]的值。

遞推公式為：dp[i] = Math.min(dp[i], dp[i - j * j] + 1)，其中 j * j <= i。

3. 初始化dp數(shù)組

Arrays.fill(dp, Integer.MAX_VALUE);

dp[0] = 0;

4. 確定遍歷順序

// 遍歷dp數(shù)組
for (int i = 1; i <= n; i++) {// 遍歷小于等于i的完全平方數(shù)j*jfor (int j = 1; j * j <= i; j++) {// 更新dp[i]dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}
}

5. 舉例推導(dǎo)dp數(shù)組

略。。。

完整代碼：

class Solution {public int numSquares(int n) {// 定義dp數(shù)組int[] dp = new int[n + 1];// 初始化dp數(shù)組Arrays.fill(dp, n+1);dp[0] = 0;// 遍歷dp數(shù)組for (int i = 1; i <= n; i++) {// 遍歷小于等于i的完全平方數(shù)j*jfor (int j = 1; j * j <= i; j++) {// 更新dp[i]dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n]; }
}

當(dāng)然，這個(gè)代碼可以再優(yōu)化一下：（使用Math的api）
減少內(nèi)層循環(huán)的次數(shù)：對(duì)于小于等于 i 的完全平方數(shù) j ，我們可以通過(guò)計(jì)算 i - j * j 的平方根得到 j 的最大值，并從最大值開(kāi)始遍歷，這樣可以減少內(nèi)層循環(huán)的次數(shù)。

class Solution {public static int numSquares(int n) {// 定義dp數(shù)組int[] dp = new int[n + 1];// 初始化dp數(shù)組Arrays.fill(dp, n + 1);dp[0] = 0;// 遍歷dp數(shù)組for (int i = 1; i <= n; i++) {// 獲取當(dāng)前數(shù)字i的最大完全平方數(shù)j*jint maxSquare = (int) Math.sqrt(i);// 遍歷完全平方數(shù)j*jfor (int j = maxSquare; j >= 1; j--) {// 更新dp[i]dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}

5 跳躍游戲

leetcode 55. 跳躍游戲

動(dòng)態(tài)規(guī)劃五部曲：

1. 確定dp數(shù)組（dp table）及其下標(biāo)的含義

dp[i]表示從起點(diǎn)位置到達(dá)位置i時(shí)能否跳躍到最后一個(gè)位置。

2. 確定遞推公式

dp[i] = (dp[j] && nums[j] >= i - j)，其中0 <= j < i

3. 初始化dp數(shù)組

初始化dp數(shù)組所有位置為false。

4. 確定遍歷順序

外層循環(huán)遍歷i從1到n-1，內(nèi)層循環(huán)遍歷j從0到i-1。

5. 舉例推導(dǎo)dp數(shù)組

以數(shù)組nums = [2, 3, 1, 1, 4]為例進(jìn)行推導(dǎo)：

初始狀態(tài)：
dp = [false, false, false, false, false]

推導(dǎo)dp[1]：
dp[1] = (dp[0] && nums[0] >= 1 - 0) = (false && 2 >= 1) = false

推導(dǎo)dp[2]：
dp[2] = (dp[0] && nums[0] >= 2 - 0) || (dp[1] && nums[1] >= 2 - 1) = (false && 2 >= 2) || (false && 3 >= 2) = false

推導(dǎo)dp[3]：
dp[3] = (dp[0] && nums[0] >= 3 - 0) || (dp[1] && nums[1] >= 3 - 1) || (dp[2] && nums[2] >= 3 - 2) = (false && 2 >= 3) || (false && 3 >= 3) || (false && 1 >= 3) = false

完整代碼如下：

class Solution {public boolean canJump(int[] nums) {// 獲取數(shù)組長(zhǎng)度int n = nums.length;// 定義dp數(shù)組boolean[] dp = new boolean[n];// 初始化dp數(shù)組dp[0] = true;// 遍歷dp數(shù)組for (int i = 1; i < n; i++) {// 內(nèi)層循環(huán)遍歷jfor (int j = 0; j < i; j++) {// 更新dp[i]dp[i] = dp[j] && nums[j] >= i - j;// 如果dp[i]為true，則跳出內(nèi)層循環(huán)if (dp[i]) {break;}}}return dp[n - 1];}
}

6 解碼方法

leetcode 91. 解碼方法

動(dòng)態(tài)規(guī)劃五部曲：

1. 確定dp數(shù)組（dp table）及其下標(biāo)的含義

dp[i]表示從字符串的起始位置到第i個(gè)字符時(shí)的解碼方法總數(shù)。

2. 確定遞推公式

對(duì)于dp數(shù)組中的每個(gè)位置i，我們需要考慮兩個(gè)情況：

• 如果第i個(gè)字符能夠單獨(dú)解碼（即不為0），則dp[i] = dp[i-1]，因?yàn)榈趇個(gè)字符自身可以作為一個(gè)解碼方法；
• 如果第i個(gè)字符與前一個(gè)字符組成的兩位數(shù)能夠解碼（即與前一個(gè)字符組成的數(shù)字在1到26之間），則dp[i] += dp[i-2]，因?yàn)榻M成的兩位數(shù)可以作為一個(gè)解碼方法。

則，遞推公式為：dp[i] = dp[i-1] + dp[i-2]，其中0 <= i < n。

3. 初始化dp數(shù)組

初始化dp數(shù)組的長(zhǎng)度為n+1，初始值為0。

4. 確定遍歷順序

for (int i = 1; i <= n; i++) {// 如果第i個(gè)字符能夠單獨(dú)解碼（即不為0）if (s.charAt(i - 1) != '0') {dp[i] += dp[i - 1];}// 如果第i個(gè)字符與前一個(gè)字符組成的兩位數(shù)能夠解碼（即與前一個(gè)字符組成的數(shù)字在1到26之間）if (i >= 2 && isValidEncoding(s.substring(i - 2, i))) {dp[i] += dp[i - 2];}
}

// 判斷字符串編碼是否在1到26之間
private static boolean isValidEncoding(String s) {if (s.charAt(0) == '0') {return false;}int num = Integer.parseInt(s);return num >= 1 && num <= 26;
}

5. 舉例推導(dǎo)dp數(shù)組

以字符串s = "226"為例進(jìn)行推導(dǎo)：

初始狀態(tài)：
dp = [1, 0, 0, 0]

推導(dǎo)dp[1]：
如果第1個(gè)字符為2，能夠單獨(dú)解碼為"2"，所以dp[1] = dp[0] = 1

推導(dǎo)dp[2]：
如果第2個(gè)字符為2，能夠單獨(dú)解碼為"2"，所以dp[2] = dp[1] = 1
如果第1個(gè)字符與第2個(gè)字符組成的兩位數(shù)為26，能夠解碼為"26"，所以dp[2] += dp[0]，即dp[2] = dp[1] + dp[0] = 1 + 1 = 2

推導(dǎo)dp[3]：
如果第3個(gè)字符為6，能夠單獨(dú)解碼為"6"，所以dp[3] = dp[2] = 2
如果第2個(gè)字符與第3個(gè)字符組成的兩位數(shù)為26，能夠解碼為"26"，所以dp[3] += dp[1]，即dp[3] = dp[2] + dp[1] = 2 + 1 = 3

最終結(jié)果：
dp = [1, 1, 2, 3]

完整代碼：

class Solution {public static int numDecodings(String s) {// 獲取字符串的長(zhǎng)度int n = s.length();// 定義dp數(shù)組int[] dp = new int[n + 1];// 初始化dp數(shù)組dp[0] = 1;// 遍歷dp數(shù)組for (int i = 1; i <= n; i++) {// 如果第i個(gè)字符能夠單獨(dú)解碼（即不為0）if (s.charAt(i - 1) != '0') {dp[i] += dp[i - 1];}// 如果第i個(gè)字符與前一個(gè)字符組成的兩位數(shù)能夠解碼（即與前一個(gè)字符組成的數(shù)字在1到26之間）if (i >= 2 && isValidEncoding(s.substring(i - 2, i))) {dp[i] += dp[i - 2];}}return dp[n];}// 判斷字符串編碼是否在1到26之間private static boolean isValidEncoding(String s) {if (s.charAt(0) == '0') {return false;}int num = Integer.parseInt(s);return num >= 1 && num <= 26;}
}

不過(guò)可以簡(jiǎn)化一下，就是比較難理解一點(diǎn)，意義一樣滴：

class Solution {public int numDecodings(String s) {int n = s.length();int[] f = new int[n + 1];f[0] = 1;for (int i = 1; i <= n; ++i) {if (s.charAt(i - 1) != '0') {f[i] += f[i - 1];}if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {f[i] += f[i - 2];}}return f[n];}
}

7 不同路徑 II

leetcode 63. 不同路徑 II

這題就是62的改版，所以復(fù)雜了很多，還是建議看代碼隨想錄：動(dòng)態(tài)規(guī)劃——不同路徑

動(dòng)規(guī)五部曲：

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

**dp[i] [j] ：**表示從（0 ，0）出發(fā)，到(i, j) 有dp[i] [j]條不同的路徑。

2. 確定遞推公式

遞推公式和62.不同路徑一樣，dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]。

但這里需要注意一點(diǎn)，因?yàn)橛辛苏系K，(i, j)如果就是障礙的話應(yīng)該就保持初始狀態(tài)（初始狀態(tài)為0）。

所以代碼為：

if (obstacleGrid[i][j] == 0) { // 當(dāng)(i, j)沒(méi)有障礙的時(shí)候，再推導(dǎo)dp[i][j]dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

3. dp數(shù)組如何初始化

因?yàn)閺?0, 0)的位置到(i, 0)的路徑只有一條，所以dp[i] [0]一定為1，dp[0] [j]也同理。

但如果(i, 0) 這條邊有了障礙之后，障礙之后（包括障礙）都是走不到的位置了，所以障礙之后的dp[i] [0]應(yīng)該還是初始值0。

如圖：

下標(biāo)(0, j)的初始化情況同理。

所以本題初始化代碼為：

int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;
}

注意代碼里for循環(huán)的終止條件，一旦遇到obstacleGrid[i] [0] == 1的情況就停止dp[i] [0]的賦值1的操作，dp[0] [j]同理

4. 確定遍歷順序

從遞歸公式dp[i] [j] = dp [i - 1] [j] + dp[i] [j - 1] 中可以看出，一定是從左到右一層一層遍歷，這樣保證推導(dǎo)dp[i] [j]的時(shí)候，dp[i - 1] [j] 和 dp[i] [j - 1]一定是有數(shù)值。

代碼如下：

for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}
}

5. 舉例推導(dǎo)dp數(shù)組

完整代碼如下：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//如果在起點(diǎn)或終點(diǎn)出現(xiàn)了障礙，直接返回0if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {return 0;}for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;}for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}

至于118，119我個(gè)人覺(jué)得并不合適使用動(dòng)態(tài)規(guī)劃的方式，所以就不寫了，over~~