C++ 931. Minimum Falling Path Sum(Leet Code)

Leet Code_931. Minimum Falling Path Sum

Dynamic Programming

 

https://leetcode.com/problems/minimum-falling-path-sum/

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

인접하게만 아래까지 길을 가면서 최소값 구하기

​

방법

1. 인접하게만 아래까지 길을 가면서 최소값 구하기

 

결과

인접하게만 아래까지 길을 가면서 최소값 구하기

 

내 코드

int nMin = INT_MAX;
void check(vector<vector<int>>& nums, int depth, int len, int nSum)
{
    nSum += nums[depth][len];
    if (depth == nums.size() - 1)
    {
        if (nSum < nMin)
            nMin = nSum;
        return;
    }
    if (len - 1 > 0)
        check(nums, depth + 1, len - 1, nSum);
    check(nums, depth + 1, len, nSum);
    if (len + 1 <= nums.size() - 1)
        check(nums, depth + 1, len + 1, nSum);
}
int minFallingPathSum(vector<vector<int>>& nums) {
    int nSum = 0;
    int depth = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        check(nums, depth, i, nSum);
    }

    return nMin;
}

테스트 케이스는 모두 통과했지만 시간 초과로 실패한 코드

아래로 내려가면서 최소값을 구했지만 시간초과란다.

 

다른사람 코드

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& a) {
        int n = a.size();
        int ans = INT_MAX;
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<n;j++){
                if(j==0){
                    if(i < n-1) a[i][j] += min(a[i+1][j],a[i+1][j+1]);
                }
                else if(j==n-1){
                    if(i < n-1) a[i][j] += min(a[i+1][j],a[i+1][j-1]);
                }
                else{
                    if(i < n-1) a[i][j] += min(a[i+1][j],min(a[i+1][j-1],a[i+1][j+1]));
                }
                if(i==0) ans = min(ans,a[i][j]);
            }
        }
        return ans;
    }
};

아래서 부터 최소값을 구하며 올라온 코드

이 코드는 성공했다.

푸는 알고리즘은 같았지만 다른 것들

1. 아래부터 위로 계산

2. 함수 호출하지않고 이중 for문

3. 합계 변수를 사용하지 않고 배열에 바로 더했다.

 

내 생각에는 함수가 재귀로 계속 호출되면서 시간 초과가 된거 같다