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