LeetCode 75 Level 1 - Day 11 Dynamic Programming

62. Unique Paths

• 題目連結
• 難易度：Medium

題目敘述

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to .

預設函數

int climbStairs(int n){

}

題目限制

• 1 <= m, n <= 100

解題過程及程式碼

本題是 Dynamic Programming的第四題，給一個 m x n 的棋盤，要從左上角走到右下角，要求出總共有幾種走法，但是只能往右走或往下走，如下圖考慮一個簡單的(m. n)=(3, 2)問題，總共有3種不同的走法：

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

想法如同之前 Dynamic Programming的題目，嘗試將大的項目分解為小的項目

• 想要走到(3, 2)要先到(2, 2)或(3, 1)，走到了(2, 2)或(3, 1)都只要一步就到目的地(3, 2)了。
• 以F(3, 2)表示從(1, 1)要走到(3, 2)的走法，F(3, 2) = F(2, 2) + F(3, 1)。
• 其中F(3, 1) = 1，因為從 (1, 1)要到 (3, 1)只有直線一種走法。
• 想要走到(3, 1)要先到(2, 1)或(3, 0)，F(3, 1) = F(2, 1) + F(3, 0)，可推論F(3, 0) = 0，所以只要F(i, j)含有1都是1，含有0的都是零，例如F(1, 0) = 0。

我們就可以寫出**F(m, n) = F(m-1, n) + F(m, n-1)**的公式

• 程式碼第一次嘗試

  int uniquePaths(int m, int n){
      if ((m == 0) || (n == 0)) return 0;
      if ((m == 1) || (n == 1)) return 1;
      return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
  }
  

  • 但這樣計算在(m. n)=(51, 9)問題時會Time Limit Exceeded。

• 考慮使用迴圈計算從F(2, 2)一直算到F(m, n)並用陣列儲存

  • F(i, 1)和F(1, j)都是1。
  • F(i, 0)和F(0, j)都是0，F(0, 1)和F(1, 0)都是0。

• 程式碼上傳

  int uniquePaths(int m, int n){
  
      /* 建立解題用的陣列 */
      int **dynArr2D = (int **)malloc(sizeof(int *) * (m+1));  /* 動態記憶體配置 */
      for (int i=0; i<(m+1); i++) {
          dynArr2D[i] = (int *)malloc(sizeof(int) * (n+1));  /* 動態記憶體配置 */
          memset(dynArr2D[i], -1, (n+1) * sizeof(int));  /* 記憶體區塊設定 -> 用來初始化 */
      }
  
      /* 填入 F(i, 1)和F(1, j)都是1 */
      /* 填入 F(i, 0)和F(0, j)都是0，F(0, 1)和F(1, 0)也都是0 */
      for (int i=0; i<(m+1); i++) {
          for (int j=0; j<(n+1); j++) {
              if ((i == 1) || (j == 1)) {
                  dynArr2D[i][j] = 1;
              }
  
              if ((i == 0) || (j == 0)) {
                  dynArr2D[i][j] = 0;
              }
          }
      }
  
      /* F(m, n) = F(m-1, n) + F(m, n-1) */
      for (int i=2; i<(m+1); i++) {
          for (int j=2; j<(n+1); j++) {
              if (dynArr2D[i][j] == -1) {
                  dynArr2D[i][j] = dynArr2D[i - 1][j] + dynArr2D[i][j - 1];
              }
          }
      }
      return dynArr2D[m][n];
  }
  

今天文章到這裡，謝謝大家!