LeetCode 62 不同路徑

---

1. 這題首先確定下dp數組下標和含義。主要有兩種方式，一種是按照位置在數組中下標直接確定，另一種是依據遞推時邊上的位置需要再往上和往左遞推時會出界，將位置設為序號而非下標。這一題第二種方式會比較好一些。
2. 遞推邏輯也是依據當前問題和子問題之間關系確定，題目中給定的是當前問題和上一個位置往下走一步以及左邊一個位置往右走一步這兩個子問題之間存在遞推關系。遞推順序依據遞推邏輯來確定的話也就是從左往右和從上往下兩重遍歷，這里我們將縱向下標設置為從上往下為增長方向，這也和內存中實際存儲方式比較相像。
3. 最后還要依據實際遞推過程確定初始化方式，這里可以用實際例子輔助思考，比如起始位置到右邊第一個格子的路徑明顯是1，由上述邏輯可以看出這里只有起始位置對應dp數組取值是1時才能滿足條件。所以dp[1][1]要初始化為1

代碼如下：

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[n + 1][m + 1];for (int i = 0; i <= n; i++) dp[i][0] = 0;for (int i = 0; i <= m; i++) dp[0][i] = 0;dp[1][1] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (i == 1 && j == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[n][m];}
}

LeetCode 63 不同路徑II

---

這題其實和上一題差不多，關鍵在于對于障礙物之后路徑遞推邏輯的處理。由于我們定下的dp數組含義是到該位置序號處的路徑數，所以直接遇到障礙物就將該到該位置路徑設為0即可。當然我們也可以在遞推過程中用if語句來判斷，但這會讓dp數組的含義變得混亂。所以不建議使用這種方法。

代碼如下：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int[][] dp = new int[obstacleGrid.length + 1][obstacleGrid[0].length + 1];for (int i = 0; i <= obstacleGrid.length; i++) dp[i][0] = 0;for (int i = 0; i <= obstacleGrid[0].length; i++) dp[0][i] = 0;dp[1][1] = (obstacleGrid[0][0] > 0 ? 0 : 1);System.out.println(dp[1][1]);for (int i = 1; i <= obstacleGrid.length; i++) {for (int j = 1; j <= obstacleGrid[0].length; j++) {if (i == 1 && j == 1) continue;dp[i][j] = (obstacleGrid[i - 1][j - 1] > 0 ? 0 : (dp[i][j - 1] + dp[i - 1][j]));System.out.print(dp[i][j] + " ");}System.out.println();}return dp[obstacleGrid.length][obstacleGrid[0].length];}
}