LeetCode.62 不同路徑
題目鏈接?不同路徑
題解
class Solution {public int uniquePaths(int m, int n) {// dp表示到達ij有多少條路徑int[][] dp = new int[110][110];dp[1][1] = 1;for(int i = 0;i<m;i++){dp[i][0] = 1;}for(int j = 0;j<n;j++){dp[0][j] = 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-1][n-1];}
}解題思路
這段代碼是用來解決不同路徑問題的動態規劃實現。下面我將詳細解析這段代碼的思路、實現細節以及可能的優化點。
一、問題背景：不同路徑問題
一個機器人位于一個?m x n?網格的左上角（起始點在下圖中標記為 “Start”）。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish”）。問總共有多少條不同的路徑？
例如，當?m=3，n=7?時，總共有 28 條不同路徑。
二、代碼思路解析
1. 動態規劃定義
dp[i][j]?表示：從左上角?(0,0)?出發，到達網格?(i,j)?時的不同路徑總數。
2. 邊界條件
- 當?
i=0（第一行）時，機器人只能一直向右移動，所以到達?(0,j)?的路徑只有 1 條，即?dp[0][j] = 1。 - 當?
j=0（第一列）時，機器人只能一直向下移動，所以到達?(i,0)?的路徑只有 1 條，即?dp[i][0] = 1。 - 代碼中初始化了?
dp[1][1] = 1，但實際通過后續對第一行和第一列的初始化，這個值會被覆蓋（若?m?和?n?大于 1），可以忽略。
3. 狀態轉移方程
- 對于網格中任意一點?
(i,j)（非第一行、非第一列），機器人只能從上方?(i-1,j)?或左方?(i,j-1)?移動而來。 - 因此，到達?
(i,j)?的路徑數 = 到達?(i-1,j)?的路徑數 + 到達?(i,j-1)?的路徑數，即：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. 遍歷順序
- 從?
i=1?到?i=m-1（行遍歷），從?j=1?到?j=n-1（列遍歷），依次計算每個網格的路徑數，最終?dp[m-1][n-1]?即為答案。
三、代碼細節說明
-
數組初始化：
int[][] dp = new int[110][110];
這里創建了一個?110x110?的二維數組，足夠覆蓋題目中常見的?m?和?n?范圍（通常題目約束?m,n <= 100）。 -
?for(int i = 0;i<m;i++){dp[i][0] = 1; // 第一列全為1 } for(int j = 0;j<n;j++){dp[0][j] = 1; // 第一行全為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-1][n-1];
由于數組下標從 0 開始，右下角的坐標為?(m-1, n-1)，直接返回該位置的路徑數即可。
四、測試案例驗證
以?m=3，n=7?為例：
- 初始化第一行?
dp[0][0..6] = [1,1,1,1,1,1,1]，第一列?dp[0..2][0] = [1,1,1]。 - 計算?
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2。 - 計算?
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3。 - ... 依次類推，最終?
dp[2][6] = 28，與預期結果一致。
LeetCode.63. 不同路徑 II
題目鏈接?不同路徑 II
題解
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[110][110];for(int i = 0;i<m;i++){if(obstacleGrid[i][0] == 1) {break;}dp[i][0] = 1;}for(int j = 0;j<n;j++){if(obstacleGrid[0][j] == 1) {break;}dp[0][j] = 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];if(obstacleGrid[i][j] == 1) dp[i][j] = 0;}}return dp[m-1][n-1];}
}解題思路
這段代碼是用來解決帶障礙物的不同路徑問題的動態規劃實現。相比基礎的不同路徑問題，這個問題增加了障礙物的限制，我們來詳細分析這段代碼的思路和實現細節。
一、問題背景：帶障礙物的不同路徑
一個機器人位于一個?m x n?網格的左上角（起始點）。機器人每次只能向下或者向右移動一步。網格中可能存在障礙物，機器人不能通過障礙物。求從左上角到右下角總共有多少條不同的路徑？
例如，對于下面的網格（1 表示障礙物）：
[[0,0,0],[0,1,0],[0,0,0]
]
答案是 2，因為有兩條不同的路徑可以避開障礙物到達終點。
二、代碼思路解析
1. 動態規劃定義
dp[i][j]?表示：從左上角?(0,0)?出發，到達網格?(i,j)?時的不同路徑總數（若?(i,j)?是障礙物，則路徑數為 0）。
2. 邊界條件處理
- 對于第一列（
j=0）：- 從?
i=0?開始遍歷，如果遇到障礙物（obstacleGrid[i][0] == 1），則后續所有單元格都無法到達（直接?break）。 - 否則，
dp[i][0] = 1（只能從上方一直向下移動到達）。
- 從?
- 對于第一行（
i=0）：- 從?
j=0?開始遍歷，如果遇到障礙物（obstacleGrid[0][j] == 1），則后續所有單元格都無法到達（直接?break）。 - 否則，
dp[0][j] = 1（只能從左方一直向右移動到達）。
- 從?
3. 狀態轉移方程
- 對于非邊界的單元格?
(i,j)：- 先計算正常情況下的路徑數：
dp[i][j] = dp[i-1][j] + dp[i][j-1]（從上方或左方到達）。 - 如果當前單元格是障礙物（
obstacleGrid[i][j] == 1），則路徑數為 0，即?dp[i][j] = 0。
- 先計算正常情況下的路徑數：
4. 最終結果
- 返回?
dp[m-1][n-1]，即到達右下角的路徑總數。
三、代碼細節說明
-
初始化網格大小：
?int m = obstacleGrid.length; int n = obstacleGrid[0].length;通過輸入的障礙物網格獲取行數?
m?和列數?n。 -
DP 數組初始化：
?int[][] dp = new int[110][110];創建一個?
110x110?的二維數組，足夠覆蓋常見的網格大小約束。 -
第一列邊界處理：
?for(int i = 0;i<m;i++){if(obstacleGrid[i][0] == 1) {break; // 遇到障礙物，后續單元格都無法到達}dp[i][0] = 1; }從頂部開始向下遍歷第一列，一旦遇到障礙物，就終止循環，確保障礙物下方的單元格路徑數保持默認的 0。
-
第一行邊界處理：
?for(int j = 0;j<n;j++){if(obstacleGrid[0][j] == 1) {break; // 遇到障礙物，后續單元格都無法到達}dp[0][j] = 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]; // 先計算正常路徑數if(obstacleGrid[i][j] == 1) dp[i][j] = 0; // 若有障礙物則路徑數為0} }雙層循環遍歷網格的非邊界部分，先按正常邏輯累加路徑數，再判斷當前位置是否為障礙物并修正路徑數。
四、測試案例驗證
以示例網格為例：
[[0,0,0],[0,1,0],[0,0,0]
]
- 初始化第一列：
dp[0][0]=1，dp[1][0]=1，dp[2][0]=1（無障礙物）。 - 初始化第一行：
dp[0][0]=1，dp[0][1]=1，dp[0][2]=1（無障礙物）。 - 計算?
dp[1][1]：先算?dp[0][1] + dp[1][0] = 2，但因?(1,1)?是障礙物，最終?dp[1][1] = 0。 - 計算?
dp[1][2]：dp[0][2] + dp[1][1] = 1 + 0 = 1（無障礙物，結果為 1）。 - 計算?
dp[2][1]：dp[1][1] + dp[2][0] = 0 + 1 = 1（無障礙物，結果為 1）。 - 計算?
dp[2][2]：dp[1][2] + dp[2][1] = 1 + 1 = 2（最終答案為 2）。
結果與預期一致，驗證了代碼的正確性。
LeetCode.96 不同的二叉搜索樹
題目鏈接?不同的二叉搜索樹
題解
class Solution {public int numTrees(int n) {int[] dp = new int[25];dp[0] = 1;for(int i = 1;i<=n;i++){for(int j = 1;j<=i;j++){dp[i] += dp[j-1] * dp[i-j]; }}return dp[n];}
}解題思路
這段代碼實現了計算不同結構的二叉搜索樹數量的功能，使用的是動態規劃的思想。
代碼解析：
-
定義了一個
numTrees方法，接收一個整數n作為參數，返回值是int類型，表示 n 個節點能組成的不同二叉搜索樹的數量。 -
創建了一個長度為 25 的數組
dp，用于存儲中間計算結果。dp[i]表示 i 個節點能組成的不同二叉搜索樹的數量。 -
初始化
dp[0] = 1，這是一個邊界條件，表示 0 個節點時只有 1 種情況（空樹）。 -
使用兩層循環計算
dp數組：- 外層循環
i從 1 到 n，表示計算 i 個節點的情況 - 內層循環
j從 1 到 i，表示以 j 為根節點的情況 - 當以 j 為根節點時，左子樹有 j-1 個節點，右子樹有 i-j 個節點
- 因此
dp[i]等于所有可能的左子樹數量乘以右子樹數量的和
- 外層循環
-
最后返回
dp[n]，即 n 個節點能組成的不同二叉搜索樹的數量
這個問題其實是一個經典的卡特蘭數（Catalan number）問題，代碼通過動態規劃的方式計算出了第 n 個卡特蘭數，也就是 n 個節點所能組成的不同二叉搜索樹的數量。
總結
以上三個問題均用動態規劃求解。62 題算 m×n 網格不同路徑數，dp [i][j] 為到 (i,j) 的路徑數，邊界為首行首列全 1，轉移方程為 dp [i][j] = 左 + 上。63 題加障礙物，遇障后首行 / 列后續為 0，當前有障則 dp 為 0。96 題算 n 個節點二叉搜索樹數，是卡特蘭數問題，dp [i] 為 i 個節點的樹數，轉移方程為左子樹數 × 右子樹數之和。
)
