1. 不同路徑（62）
題目描述：
狀態(tài)表示：
設dp[i][j]表示到達(i,j)位置時的路徑數(shù)目。
狀態(tài)轉移方程：
dp[i][j]=dp[i-1][j]+dp[i][j-1]。這里分析起來很簡單，因為這算是很經典的問題了。機器人只能向下或者向右走，所以到達(i,j)就有兩種方式，分別是從(i-1,j)向下以及(i,j-1)向右，那么到達(i,j)位置的路徑數(shù)只需要將到達(i-1,j)以及(i,j-1)位置的路徑數(shù)相加即可。
初始化：
初始化就是為了避免越界問題，因為這里的狀態(tài)轉移方程涉及到i-1以及j-1。這里可以在矩陣外添加一行和一列，至于對于一行和一列的初始化要注意不能影響最終輸出的結果，另外這樣初始化還要注意下標的映射關系，這東西講不清具體得看代碼，這樣初始化的好處就是可以將一整個矩陣全寫進循環(huán)。
填表順序：
從上到下，從左至右。
返回值：
因為添加了一行一列所以返回dp[m][n]。
代碼如下：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m + 1][n + 1];
dp[0][1] = 1;
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];
}
}
return dp[m][n];
}
}
題目鏈接
時間復雜度:O(n^2)
空間復雜度:O(n^2)
2. 不同路徑 II（63）
題目描述:
狀態(tài)表示：
和上一題一樣(i,j)位置的路徑數(shù)為dp[i][j]。
狀態(tài)轉移方程：
實際上這題的狀態(tài)轉移方程也非常類似于上一題，但是要考慮一個特殊情況，就是障礙的情況。當(i,j)是障礙物的情況下直接將dp[i][j]=0,當(i,j)不是障礙物的情況下dp[i][j]=dp[i-1][j]+dp[i][j-1]。
初始化：
這里的初始化和上一題是一致的額，沒什么好說的。。但是要提前判斷左上角為障礙物的情況，直接返回0。
填表順序：
從上往下，從左至右。
返回值：
與上題一致也是返回dp[m][n]。
代碼如下：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m + 1][n + 1];
dp[0][1] = 1;
if (obstacleGrid[0][0] == 1) {
return 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (obstacleGrid[i - 1][j - 1] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m][n];
}
}
題目鏈接
時間復雜度:O(n^2)
空間復雜度:O(n^2)
3. 珠寶的最高價值（LCR 166）
題目描述:
狀態(tài)表示：
這題與上面兩題也是相似的，只不過給出的矩陣多出了一個值的屬性，說白了這篇博客就是將路徑問題進行的一個分類總結。這題的狀態(tài)表示根據(jù)經驗和題目要求可以設置為dp[i][j]表示在(i,j)位置能夠拿到的最大珠寶價值。
狀態(tài)轉移方程:
到達(i,j)位置還是只能夠從(i-1,j)以及(i,j-1),因此要得到(i,j)位置的最大價值首先要將dp[i-1][j]與dp[i][j-1]的價值進行比較得到最大值賦給dp[i][j]，狀態(tài)轉移方程為dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]。
初始化：
還是類似加上一行和一列，但是這里不用做別的操作了，行和列賦0即可。但是還要注意dp數(shù)組與frame數(shù)組的映射關系。
填表順序：
從上到下，從左至右。
返回值：
dp[m][n]。
代碼如下：
class Solution {
public int jewelleryValue(int[][] frame) {
int m = frame.length;
int n = frame[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
}
}
return dp[m][n];
}
}
題目鏈接
時間復雜度:O(n^2)
空間復雜度:O(n^2)
4. 下降路徑最小和（931）
題目描述：
狀態(tài)表示：
根據(jù)經驗加題目要求可以將dp[i][j]定義為到達(i,j)位置的最小路徑和。
狀態(tài)轉移方程：
(i,j)上一行相鄰的位置有(i-1,j)(i-1,j-1)(i-1,j+1),因此要求得到達(i,j)位置的最小路徑和就可以列出以下狀態(tài)轉移方程，dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+ matrix[i][j]。
初始化：
要避免到達(i,j)位置的前三個位置越界可以在矩陣上加上左右兩邊的兩列以及上邊的一行，從而方便后續(xù)的操作，這里為了避免加上的空間影響最終得到的結果要注意把加上的一行賦值為0，加上的兩列賦值為無窮大。
填表順序：
從上到下，從左至右。
返回值：
要返回矩陣最后一行的最小值。
代碼如下：
class Solution {
public int minFallingPathSum(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 2];
for (int i = 0; i <= m; i++) {
dp[i][0] = Integer.MAX_VALUE;
}
for (int i = 0; i <= m; i++) {
dp[i][n + 1] = Integer.MAX_VALUE;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
}
}
int min = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
if (min > dp[m][i]) {
min = dp[m][i];
}
}
return min;
}
}
題目鏈接
時間復雜度:O(n^2)
空間復雜度:O(n^2)
5. 最小路徑和（64）
題目描述:
狀態(tài)表示：
經驗加題目要求，設定dp[i][j]表示到達(i,j)位置的最小路徑和。
狀態(tài)轉移方程：
因為只能向下以及向右移動，所以dp[i][j]的值關聯(lián)于dp[i-1][j]以及dp[i][j-1],即dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j]。
初始化：
也是一樣為了避免越界，要給dp加上一行和一列的空間，這里要考慮到不能影響到最終的結果，因此除了左上角的左邊和上邊的空間其余空間都賦為無窮大。
填表順序：
從上到下，從左至右。
返回值：
因為增加了一行和一列，所以應該返回dp[m][n]。
代碼如下：
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < n + 1; i++) {
dp[0][i] = Integer.MAX_VALUE;
}
for (int i = 0; i < m + 1; i++) {
dp[i][0] = Integer.MAX_VALUE;
}
dp[0][1] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
}
}
return dp[m][n];
}
}
題目鏈接
時間復雜度:O(n^2)
空間復雜度:O(n^2)
6. 地下城游戲（174）
題目描述：
狀態(tài)表示：
根據(jù)經驗以及題目要求這題定義dp[i][j]為以(i,j)為起點到達終點所需的最小點數(shù)。
狀態(tài)轉移方程：
根據(jù)經驗與題目要求dp[i][j]定義為以位置(i,j)為起點營救公主所需的最低血量。因此位置(i,j)和其下邊以及右邊的dp元素的關系如下：
dp[i][j]+dungeon[i][j]>=dp[i+1][j]。
dp[i][j]+dungeon[i][j]>=dp[i][j+1]。
要滿足以上條件，皆取最小值，即dp[i][j]=min(dp[i+1][j]-dungeon[i][j],dp[i][j+1]-dungeon[i][j])，不過要注意一個問題，當dungeon[i][j]的值是一個很大的值即一個很大的血包的時候，dp[i][j]就為負值了，要避免這種情況，如果出現(xiàn)血包很大的情況就將dp[i][j]直接賦為1即可，因為1就是邏輯上合理的最低血量。
初始化：
為了避免越界也要在dp上再多加一行和一列，這里的行和列是加在最后一行和最后一列。為了使添加之后不影響輸出的結果，所以在行和列的每一個空間賦無窮大，只有右下角公主所在的位置的右邊和下邊賦為1，因為在邏輯上當營救完公主之后血量至少為1。
填表順序：
從下到上，從右至左。
返回值：
dp[0][0]。
代碼如下:文章來源：http://www.zghlxwxcb.cn/news/detail-853881.html
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][n] = Integer.MAX_VALUE;
}
for (int i = 0; i <= n; i++) {
dp[m][i] = Integer.MAX_VALUE;
}
dp[m][n - 1] = 1;
dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = Math.max(1, dp[i][j]);
}
}
return dp[0][0];
}
}
題目鏈接
時間復雜度:O(n^2)
空間復雜度:O(n^2)文章來源地址http://www.zghlxwxcb.cn/news/detail-853881.html
到了這里，關于動態(tài)規(guī)劃-路徑問題的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
