關於Leetcode上一道題目用動態規劃求解的探究？

01-16

問題如下：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizesthe sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
我的求解方法如下：
public class Solution {

public int minPathSum(int[][] grid) {
/****考慮如下問題，如何用一維DP求解呢？即用到的空間最小為min(row,col)***/
int row=grid.length;
int col=grid[0].length;
if(row==0col==0)
return 0;
int[][] res=new int[row][col];
res[0][0]=grid[0][0];//initial
for(int i=1;i& res[i][0]=res[i-1][0]+grid[i][0];

for(int j=1;j& res[0][j]=res[0][j-1]+grid[0][j];
for(int i=1;i& for(int j=1;j& {
res[i][j]=Math.min(res[i-1][j],res[i][j-1])+grid[i][j];
}
return res[row-1][col-1];
}
}

我想問的是，我記得看過這種題目有一維動態規劃解法，空間只用到O(min(row,col)),這裡想問一維怎麼求解？why？

滾動數組

因為這題中DP數組每個格子dp[i][j]只依賴它左邊一格dp[i][j-1]和上邊一格dp[i-1][j]的值，

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]

二層循環不變，數組用一維數組取代，則是

dp[j] = min(dp[j-1], dp[j]) + grid[i][j]

此處min()中dp[j-1]是上一個內層循環算出來的，dp[j]則相當於二維數組中dp[i-1][j]。

滾動數組只壓縮空間，時間上可能會有犧牲，因為有時要存儲/更新更多臨時變數

這個問題很早之前做過，當時採用的就是題主寫的二維數組做法。近期系統地重溫了一下動態規劃，發現很多二維數組問題都可以用一維數組來做~剛剛把這題用一維數組實現了一下，先貼代碼吧：

public class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return -1; int[] dp = new int[grid[0].length]; dp[0] = grid[0][0]; for(int i = 1; i &< grid[0].length; i++) { dp[i] = dp[i - 1] + grid[0][i]; } for (int i = 1; i &< grid.length; i++) { dp[0] = dp[0] + grid[i][0]; for (int j = 1; j &< grid[i].length; j++) { dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j]; } } return dp[grid[0].length - 1]; } }

關鍵就在於dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]中每次結果只與上行和左列結果有關，所以可以轉換為一維數組dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j]，其中括弧內dp[j - 1]表示左列的結果，dp[j]表示上行的結果。

類似地，許多隻與上一狀態和上一結果有關的問題也都可以用一維數組來在循環內部動態更新結果。還有一些甚至可以通過幾個變數來做。best time to buy and sell stock |||就是一個典型的例子。可以實現二維數組--&>一維數組--&>四個變數的O(n^2)--&>O(n)--&>O(1)空間複雜度優化。這個問題寫過一點筆記Best Time to Buy and Sell Stock系列，題主可以參考一下O(∩_∩)O~

樓主已經知道怎麼dp了，就是說第i行的狀態只能從上一行轉移過來。

所以你只用保留上一行的狀態用來推導當前行就可以了。

所以用滾動數組可以做到O(n)

首先：如果列比行長則交換行列。

然後即可寫出正經公式：F[i][j]=min(F[i-1][j]+C,F[i][j-1]+C)

進一步，考慮削減變元，當然這裡只有兩個變元，削減不了。

削減完變數後就可以認認真真考慮如何安排空間了。

具體原則是：只要保存好F[n][m]值即可，其他值管他去死。

為了達到這個目的，就要正確計算F[i][j]。為了正確計算F[i][j]，就要使得F[i-1][j]及F[i][j-1]的值在計算F[i][j]時未被覆蓋。

實際上就是一個空間分配問題。

在競賽中有一種非常無賴的辦法:只保存最外層變元最後幾列的值。

在這裡即：F[i%2][j]=min(F[(i-1+2)%2][j],F[i%2][j-1])

設bool b，有F[b][j]=min(F[!b][j],F[b][j-1])

如果這樣還爆空間的話，可以在固定i的情況下再對F[fixed][j]實施此方法，然後把需要保存的值再摘出來。

再爆，再嵌套。再爆，再嵌套。再爆，再嵌套。再爆，再嵌套。

憑此方法再競賽中未曾一擺，很好的掩蓋了我做題不靠腦子的事實。_(:з」∠)_

善用lc discuss，你要的O(n) space裡面就有

一條45度的斜線,假設r&<=c，(0,0);(0,1)(1,0);.......;(0,r)(1,r-1)(2,r-2).....(r,0);(1,r)(2,r-1)......(r,1)........

只要保存邊緣就行了

當然可以，這樣考慮，最底層的一行沒有選擇，只能選擇往右走，在我們把一層填完以後，其上面一層的最優解是可以根據他下面這一層的信息得出最優解的，然後下面這一層就不需要了，所以我們只需要維護一層的數組即可，下面是O(row)的演算法，O(min(row, col))多一次比較，方法是一樣的

這是運行結果

這裡如果想保存minSum的path，可以加一個int型變數，right用1表示，down用0表示，那麼整個路徑就是一串二進位，但是有可能會因為路徑太長（二維數組太大）導致越界

e.g. int a = 13 = 1101(2)，表示路徑為r-&>r-&>d-&>r

思路僅供參考

1. 典型的解法就是用O(mn)的空間。 int minPathSum(vector&&> grid) { // memo[i][j] means min path from grid[0][0] to grid[i][j]. vector&&> memo = grid; int row = grid.size(), int col = grid[0].size();


  for (int i = 0; i &< row; ++i) {
    for (int j = 0; j &< col; ++j) {
      int top = i &< 1? INT_MAX : memo[i-1][j];
      int left= j &< 1? INT_MAX : memo[i][j-1];
      memo[i][j] +=(i | j)? min(top, left) : 0; // &

    }

  }

  return memo[row-1][col-1];

}
2.

但是注意到，我們可以直接在grid數組上進行修改。所以就完全避免了額外的空間開銷

int minPathSum(vector&&> grid) {

  int row = grid.size(), col = grid[0].size();

for (int i = 0; i &< row; ++i) { for (int j = 0; j &< col; ++j) { int top = i &< 1? INT_MAX : grid[i-1][j]; int left= j &< 1? INT_MAX : grid[i][j-1]; grid[i][j] +=(i|j)? min(top, left) : 0; } } return grid[row-1][col-1]; }

實際上最小的space就是只保留會影響後面結果的數，原理不複雜，只是有時候操作起來會很蛋疼，不美觀。