C++での最小立ち下がりパス合計II

グリッドarrがあるとします。これは正方形のグリッドであり、ゼロ以外のシフトを伴う立ち下がりパスは、隣接する行で選択された2つの要素が同じ列に存在しないように、arrの各行から正確に1つの要素を選択します。ゼロ以外のシフトを伴う立ち下がりパスの最小合計を見つける必要があります。

したがって、入力がarrが[[1,2,3]、[4,5,6]、[7,8,9]]のようである場合、異なる立ち下がりパスがあるため、出力は13になります。これらは、[1,5,9]、[1,5,7]、[1,6,7]、[1,6,8]、[2,4,8]、[2,4,9]のようなものです。 、[2,6,7]、[2,6,8]、[3,4,8]、[3,4,9]、[3,5,7]、[3,5,9]。現在、合計が最小の下降経路は[1,5,7]であるため、答えは13です。

これを解決するには、次の手順に従います-

• n：=行数、m：=列数

• 初期化i：=1の場合、i

  • サイズmの配列leftMinとrightMinを定義します

  • leftMin [0]：=arr [i-1、0]

  • 初期化j：=1の場合、j

    • leftMin [j]：=leftMin[j-1]とarr[i-1、j]

      の最小値

  • rightMin [m-1] =arr [i-1、m-1]

  • 初期化j：=m-2の場合、j> =0の場合、更新（jを1つ減らす）、実行-

    • rightMin [j]：=最小のarr [i-1、j]およびrightMin [j + 1]

  • 初期化j：=0の場合、j

    • leftVal：=（（j --1）> =0の場合、leftMin [j -1]、それ以外の場合は1000000）

    • rightVal：=（（j + 1）

    • arr [i、j]：=arr [i、j] + min（leftVal、rightVal）

• ans：=inf

• 初期化i：=0の場合、i

  • ans：=最小のansとarr [n-1、i]

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
int dp[10005][205];
class Solution {
   public:
   void pre(){
      for(int i = 0; i <= 10000; i++){
         for(int j = 0; j <=204; j++){
            dp[i][j] = -1;
         }
      }
   }
   int minFallingPathSum(vector<vector<int>>& arr) {
      int n = arr.size();
      int m = arr[0].size();
      for (int i = 1; i < n; i++) {
         vector<int> leftMin(m);
         vector<int> rightMin(m);
         leftMin[0] = arr[i - 1][0];
         for (int j = 1; j < m; j++) {
            leftMin[j] = min(leftMin[j - 1], arr[i - 1][j]);
         }
         rightMin[m - 1] = arr[i - 1][m - 1];
         for (int j = m - 2; j >= 0; j--) {
            rightMin[j] = min(arr[i - 1][j], rightMin[j + 1]);
         }
         for (int j = 0; j < m; j++) {
            int leftVal = (j - 1) >= 0 ? leftMin[j - 1] :
            1000000;
            int rightVal = (j + 1) < m ? rightMin[j + 1] :
            1000000;
            arr[i][j] += min(leftVal, rightVal);
         }
      }
      int ans = INT_MAX;
      for (int i = 0; i < m; i++)
      ans = min(ans, arr[n - 1][i]);
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   cout << (ob.minFallingPathSum(v));
}

入力

{{1,2,3},{4,5,6},{7,8,9}}

出力

13