第25個冬天

 問題敘述如下： 這個問題是 "Unique Paths" 的變體，但現在網格中包含一些障礙物。給定一個包含障礙物和空格的 m x n 網格，請找出從左上角到右下角的不同不含障礙物的獨特路徑數量。 障礙物和空格分別用 1 和 0 來表示。 有多少種不同的獨特路徑可以達到終點？ 注意：m 和 n 最大不超過 100。 [   [0,0,0],   [0,1,0],   [0,0,0] ] 從左上角到右下角的不同不含障礙物的獨特路徑數為 2。 這個問題可以使用動態規劃（Dynamic Programming）解決，類似於 "Unique Paths" 問題。我們仍然使用一個二維數組 dp，其中 dp[i][j] 表示到達從左上角 (0, 0) 到 (i, j) 這個格子的不同獨特路徑數。但是，我們需要注意處理障礙物。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: int uniquePathsWithObstacles(std::vector<std::vector< int >>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[ 0 ].size(); // 如果起點或終點有障礙物，則無法到達終點，返回 0。 if (obstacleGrid[ 0 ][ 0 ] == 1 || obstacleGrid[m- 1 ][n- 1 ] == 1 ) return 0 ; // 創建大小為 (m x n) 的二維 DP 數組。 std::vector<std::vector< int >> dp(m, std::vector< int >(n, 0 )...

題目描述： 給定一個 m x n 的網格，從左上角出發， 每次只能向右或向下移動一步 ，要到達右下角，有多少不同的路徑？ 解題思路： 若直接沿用題目要的規則下去思考會比較困難 不過這邊有個淺藏的規律 start -> finish ⽅方法數 = finish -> start ⽅方法數  那我們可反過來思考Finish走到start的方法數會較簡單 最下⾯面的 row及最右邊的 column，通往 finish 的⽅方法只有1種。可藉此反推走向 start 的⽅方法：通往某座標的⽅方法數 = 下⾯面座標的⽅方法數 + 右邊座標的⽅方法數 這是一個典型的動態規劃問題，我們可以使用動態規劃的方法來解決它。我們建立一個二維數組 dp，其中 dp[i][j] 表示從左上角到達網格中位置 (i, j) 的不同路徑數。 首先，我們可以初始化 dp[0][0] 為 1，因為左上角的位置就是起點，只有一種方法到達它。接下來，我們可以使用遞歸關係式來計算 dp[i][j]，即： dp[i][j] = dp[i-1][j] + dp[i][j-1] 這是因為要到達位置 (i, j)，我們可以從上方的位置 (i-1, j) 或左方的位置 (i, j-1) 移動過來，所以 dp[i][j] 等於這兩個位置的不同路徑數之和。 我們需要進行雙重迴圈遍歷整個網格，從 (0, 0) 開始遍歷到 (m-1, n-1)。最後，dp[m-1][n-1] 就表示從左上角到達右下角的不同路徑數。 第一種作法.DP class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 && j == 0) { dp[i][j] = 1; } else { ...

題目描述： 你正在爬樓梯。樓梯有 n 階，每次你可以爬 1 階或 2 階。你想要到達樓梯的頂部，有多少種不同的方法可以達到頂部？ 可以使用動態規劃的方法來解決這個問題，建立一個長度為 n+1 的數組 dp，其中 dp[i] 表示爬到第 i 階樓梯的不同方法數。 我們可以初始化 dp[0] 為 1，因為爬到第 0 階樓梯的方法只有一種，就是不動。同樣地，dp[1] 也為 1，因為爬到第 1 階樓梯的方法只有一種，就是爬一階。接下來，我們可以使用遞歸關係式來計算 dp[i]，即： dp[i] = dp[i-1] + dp[i-2] 這是因為要到達第 i 階樓梯，我們可以從第 i-1 階樓梯爬一階，或者從第 i-2 階樓梯爬兩階。這樣我們就可以不斷地更新 dp 數組，直到計算出 dp[n]，它表示到達頂部的不同方法數。 從 n > 2 開始，到達 n - 1 階和 n - 2 階的⽅方法數都已知了了： n - 1 階到達第 n 階只有⼀一種⽅方法：走⼀一次⼀一步 n - 2 階到達第 n 階有兩兩種⽅方法：走兩兩次⼀一步、走⼀一次兩兩步。但第⼀一種⽅方法和 n - 1 階到 n 階重複，不予考慮 承上，到 (n - 1) 及 (n - 2) 後，可以到達 n 的可能選項已被固定，0 -> n ⽅方法數 = 0 -> (n - 1) ⽅方法數 + 0 -> (n - 2) ⽅方法數 Dynamic Programming(DP) 常⽤用思維：a -> b 只有⼀一個選項，代表通往終點的可能選項已經被固定住了了。因為可能選項已經被固定住了了，程式只需計算到前⼀一步。 Dynamic Programming： 每次的運算結果，都是基於此前以同⼀一個邏輯運算的結果   -> f(n) = f(n - 1) + f(n - 2) class Solution { public: int climbStairs(int n) { if (n <= 1) { return 1; // 當 n <= 1 時，只有一種方法 } vector<int> dp(n + 1, 0); dp[0] = 1; ...