LeetCode || Minimum Path Sum

Minimum Path Sum  
Total Accepted: 19916 
Total Submissions: 63796 My Submissions
Question  Solution 
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
題意:m x nのメッシュで、各格子に非負の整数があり、左上から右下への経路を見つけ、通過する格子の数値の和を最小にし、一歩ごとに右または下にしかできない.
分析:これは典型的な動的計画問題であり、動的計画を使用して問題を解き、最も重要なのは動的計画の3要素を確定することである:問題の段階、各段階の状態、および前の段階から後の段階への間の繰返し関係.繰返し関係は次数の小さい問題から大きな問題への転換でなければならないが,この観点から動的計画は往々にして繰返しプログラムで実現できるが,繰返しは前に保存したサブ問題の解を十分に利用して繰返し計算を減らすことができるため,大規模な問題に対しては繰返しとは比べものにならない利点がある.これも動的計画アルゴリズムの核心である.動的計画のこの3つの要素を決定し,解の過程全体を最適決定テーブルで記述することができ,最適決定テーブルは2次元テーブルであり,行は決定の段階を表し,列は問題状態を表す.表に記入する必要があるデータは一般的にこの問題に対応するある段階のある状態における最適値(例えば最短経路、最長共通サブシーケンス、最大価値など)であり、表を記入する過程は繰返し関係に基づいて1行1列から行または列優先の順序で順次表に記入することである.最後に,表全体のデータから簡単な取捨選択や演算により問題の最適解を求める.
この問題ではまず,各格子i,jの最小経路和を格納する2次元配列をMPS[i][j]とするなど,繰返し関係を見つけることができるが,繰返し式は次のようになる.
MPS[i][j] = Min(MPS[i-1][j],MPS[i][j-1])+ val[i][j];
すなわち、格子i,jのMPS値には、左側の格子i,j−1またはその上側の格子i−1,jの2つのソースがある可能性がある.この2つのソースの小さいMPS値をとり,現在の格子の値val[i][j]を加えると結果となる.
左上から右下に進むので、ある格子を計算するたびに左側の格子と上側の格子の結果が計算されるので、二重サイクルを利用して反復計算を行うことができます.これもダイナミックプランニングが再帰よりも速い理由です.
コードは次のとおりです.

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        if(grid.size()==0)
            return 0;
        vector<vector<int>> res(grid);
        int i, j;
        for(int j=1; j<res[0].size(); ++j){
            res[0][j] += res[0][j-1];
        }
        for(int j=1; j<res.size(); ++j){
            res[j][0] += res[j-1][0];
        }
        for(i=1; i<res.size(); ++i){
            for(int j=1; j<res[i].size(); ++j){
                res[i][j] = min(res[i-1][j], res[i][j-1])+grid[i][j];
            }
        }
        return res[grid.size()-1][grid[0].size()-1];    //     size     
    }
};

Nを格子総数(N=m*n)とし、上のコード空間複雑度をO(N)、時間複雑度をO(N)とする.gridの値を直接変更できれば、新しい配列空間を申請する必要はありませんが、通常gridの値を変更することはできません.空間の複雑さを知らないでまだ最適化の方法がありますか?交流を歓迎します~~
方法2:再帰戦略を採用し、右下の終点から前方に再帰し、問題の最適解包含子問題の最適解という思想を利用して、段階的に再帰し、起点まで、すなわち:
int  MinRecursive(i,j){
if( i==0 && j==0)
return val[0][0];
if(i==-1 || j==-1)
return無限大;//境界状況に注意
return Min(MinRecursive(i-1, j),MinRecursive(i,j-1))+val[i][j];
}