그리드 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