遞歸和動态規劃——矩陣的最小路徑和

《程式員代碼面試指南》

動态規劃問題

左上角到右下角，隻能向下一步或者向右一步。

矩陣m的大小M*N，dp[i][j]表示從左上角到（i，j）的最小路徑。dp[M][N]是答案。

第一行比較特殊，(0,0)到(0,j)隻能向右，是以路徑和是疊加。

第一列同理，(0,0)到(i,0)隻能向下，路徑和也是疊加。

此外的位置，dp[i][j] = min(dp[i-1][j],dp[i][j-1])+m[i][j]

//借鑒了牛客上的一些答案和書上答案
#include <vector>
#include <iostream>
using namespace std;
int minPathSum(vector<vector<int>> m){
        int row =m.size();
        int col = m[0].size();
        vector<vector<int>> dp(row,vector<int>(col,0));
        dp[0][0] = m[0][0];
        for (int i = 1; i< row; i++){
            dp[i][0]=dp[i-1][0]+m[i][0];
        }
        for (int j = 1; j< col; j++){
            dp[0][j]=dp[0][j-1]+m[0][j];
        }
        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j< col; j++){
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+m[i][j];
            }
        }
        return dp[row-1][col-1];
}
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') {
            ch = getchar();
            flag = -1;
            break;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ans = (ans << 3) + (ans << 1) + ch - '0';
        ch = getchar();
    }
    return ans * flag;
}

int main() {
    int N, M;
    N = read();
    M = read();
    vector<vector<int>> a(N,vector<int>(M,0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            a[i][j] = read();
        }
    }
    cout<<minPathSum(a);
    return 0;
}
           

另外看到一個這麼寫的，感覺這樣讀取輸入很友善（太久沒寫c++了，多積累點是一點T T）

vector<vector<int> >a;
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
        {
            vector<int>temp;
            for(int j=0;j<m;j++)
            {
                int tmp;
                cin>>tmp;
                temp.push_back(tmp);
            }
            a.push_back(temp);
        }
        cout<<minPathSum(a)<<endl;
    }
           

壓縮空間的方法：

int minPathSum(vector<vector<int>> m){
        int row =m.size();
        int col = m[0].size();
        //vector<vector<int>> dp(row,vector<int>(col,0));
        int more = max(row,col);
        int less = min(row,col);
        bool rowmore= more==row;
        int dp[less];
        dp[0] = m[0][0];
        for(int i=1;i<less;i++){
            dp[i] = dp[i-1]+(rowmore?m[0][i]:m[i][0]);
        }
        for (int i = 1;i < more; i++)
        {    dp[0] = dp[0]+(rowmore?m[i][0]:m[0][i]);
            for (int j = 1; j< less; j++){
                dp[j] = min(dp[j-1],dp[j])+(rowmore?m[i][j]:m[j][i]);
            }
        }
        return dp[less-1];
}
           

如果行數多，先将數組初始化dp[less],dp[j]為(0,0)到(0,j)的最小路徑和。

看(1,0)，dp[0] = dp[0]+m[1][0].

(1,1)，dp[1]=min(dp[0]+dp[1])+m[1][1]

…

不斷滾動更新數組。