Tổng đường đi xuống tối thiểu II trong C ++

Giả sử chúng ta có một lưới arr, đây là một lưới vuông, một đường đi xuống với các dịch chuyển khác 0 là sự lựa chọn của chính xác một phần tử từ mỗi hàng của arr, sao cho không có hai phần tử được chọn trong các hàng liền kề có mặt trong cùng một cột. Chúng ta phải tìm tổng nhỏ nhất của một đường đi xuống với các dịch chuyển khác không.

Vì vậy, nếu đầu vào giống arr như [[1,2,3], [4,5,6], [7,8,9]], thì đầu ra sẽ là 13, vì có các đường đi xuống khác nhau, chúng giống như [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]. Bây giờ đường đi xuống với tổng nhỏ nhất là [1,5,7], vì vậy câu trả lời là 13.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=số hàng, m:=số cột

• để khởi tạo i:=1, khi i

  • Xác định mảng leftMin và rightMin có kích thước m

  • leftMin [0]:=arr [i - 1, 0]

  • để khởi tạo j:=1, khi j

    • leftMin [j]:=tối thiểu leftMin [j - 1] và arr [i - 1, j]

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

  • để khởi tạo j:=m - 2, khi j> =0, cập nhật (giảm j đi 1), thực hiện -

    • rightMin [j]:=tối thiểu arr [i - 1, j] và rightMin [j + 1]

  • để khởi tạo j:=0, khi j

    • leftVal:=(if (j - 1)> =0, then leftMin [j - 1], if not 1000000)

    • rightVal:=(if (j + 1)

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

• ans:=inf

• để khởi tạo i:=0, khi i

  • ans:=tối thiểu ans và arr [n - 1, i]

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

13