C ++中的最小下降路径总和II

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个网格arr，这是一个正方形网格，具有非零偏移的下降路径是从arr的每一行中选择一个元素，这样在同一列中就不会出现在相邻行中选择的两个元素。我们必须找到非零位移的下降路径的最小和。

因此，如果输入像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 <n时，更新（将i增加1），-

    • leftVal：=（如果(j-1)> = 0，则为leftMin [j-1]，否则为1000000）

    • rightVal：=（如果（j + 1）<m，则rightMin [j + 1]，否则1000000）

    • arr [i，j]：= arr [i，j] + min(leftVal,rightVal)

    • rightMin [j]：= arr [i-1，j]和rightMin [j + 1]的最小值

    • leftMin [j]：= leftMin [j-1]和arr [i-1，j]的最小值

    • 定义大小为m的leftMin和rightMin数组

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

    • 对于初始化j：= 1，当j <m时，更新（将j增加1），-

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

    • 对于初始化j：= m-2，当j> = 0时，更新（将j减1），执行-

    • 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

    • ans：= inf

    • 对于初始化i：= 0，当i <m时，更新（将i增加1），执行-

      • 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

    以上是 C ++中的最小下降路径总和II 的全部内容， 来源链接： utcz.com/z/316327.html

    回到顶部