Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 최소 낙하 경로 합계 II

<시간/>

그리드 arr가 있다고 가정합니다. 이것은 정사각형 그리드입니다. 0이 아닌 이동이 있는 하강 경로는 arr의 각 행에서 정확히 하나의 요소를 선택하므로 인접한 행에서 선택된 두 요소가 동일한 열에 존재하지 않습니다. 0이 아닌 이동이 있는 하강 경로의 최소 합을 찾아야 합니다.

따라서 입력이 [[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 :=열 수

  • initialize i :=1의 경우 i

    • m 크기의 배열 leftMin 및 rightMin 정의

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

    • initialize 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 :=(if (j - 1)>=0이면 leftMin[j - 1]이고 그렇지 않으면 1000000)

      • rightVal :=((j + 1)

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

  • ans :=inf

  • initialize i :=0의 경우 i

    • ans :=ans 및 arr[n - 1, i]

      의 최소값
  • 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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