力ボタン62の異なる経路【動的計画五段階法】

力ボタン62の異なる経路【動的計画五段階法】
文書ディレクトリ

力ボタン62異なる経路【動的計画五段階法】

すべてのブラシ問題と学習記録

原題

考査知識点

良い解法

すべてのブラシと学習記録
【C++ブラシ学習ノート目録】
【C++100万同時ネットワーク通信-ノートディレクトリ】
原題
タイトルアドレス:62.異なるパス
ロボットはm x nメッシュの左上隅にあります(開始点は下図で「Start」と表記されています).
ロボットは毎回、下または右に1歩しか移動できません.ロボットはメッシュの右下隅に到達しようとします(下図では「Finish」と表記されています).
全部で何本の違う経路がありますか?
例1:

  ：m = 3, n = 7
  ：28

例2:

  ：m = 3, n = 2
  ：3
  ：
      ，    3           。
1.    ->    ->   
2.    ->    ->   
3.    ->    ->   

知識点を考査する.
動的計画、dp配列の理解
よい解法
正直に言うと、この問題の最初の直感は遡及で行われています.剣指12行列の中の経路は似たような問題環境だからです.しかし、「コード随想録」のオヤジのダイナミックプランニング五歩法でこの問題を作るのは素晴らしい.問題解を見ないうちに、この問題がまだゲージでできるとは思えない.やはり理解が深くない.やはり、次の状態と現在の状態に関係するものはダイナミックプランニングに頼らなければならない.
参照先:
https://mp.weixin.qq.com/s/MGgGIt4QCpFMROE9X9he_A
動的に計画されたdp配列は1次元に限られるものではなく,この問題のようなdp配列は2次元形式である.
1、dp配列(dp table)および下付き文字の意味を決定する
dp配列が表す意味は一般に問題要求の答えである.dp[i][j]は、（0,0）から（i,j）までの経路の数を示す.
2、繰返し式を確定する
テーマは、ロボットは下へ、右へしか行けないので、(i,j)のロボットは(i-1,j)、(i,j-1)の2つの方向からしか来られません.
つまりdp[i][j] = dp[i-1][j] +dp[i][j-1]3、dp配列の初期化方法
dp配列が1次元の場合、dp[0]を初期化するだけで、最大1つのdpを追加することができる[1].ではdp配列が2次元の場合、2次元配列のエッジは2つのエッジ、すなわちdp[i][0]=1、dp[0][j]=1である.2 D配列の2つのエッジが1つになっているのは、ロボットが下、右にしか歩けないためです.2つのエッジに到達するには(0,0)からまっすぐ行かなければなりません.
4、遍歴順序の決定
左から右へ,上から下へ,dp配列の各数を徐々に算出する
5、例を挙げてdp配列を導く
例えばm=4,n=3

1  1  1
1  2  3
1  3  6
1  4  10

class Solution {
     
public:
    int uniquePaths(int m, int n) {
     
        if (m <= 1) return m;
        if (n <= 1) return n;

        vector<vector<int>> dp;
        dp.resize(m, vector<int> (n));

        //dp     
        for (int i = 0; i < m; ++i) {
     
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
     
            dp[0][j] = 1;
        }
        //  
        for (int i = 1; i < m; ++i) {
     
            for (int j = 1; j < n; ++j) {
     
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
};

int main() {
     
    Solution so;
    cout << so.uniquePaths(3, 7);
}