minimum-path-sum

gistfile1.txt

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

/*
초기 접근: 
전수조사를 해야하는가->그렇다. 
어떻게 가지치기 할 것인가-> dp 적용

base case 설정: 
if left == m-1, down == n-1

dp 적용:
dp를 적용하기 위해서는 처음에 짤때부터 dp를 어떻게 적용할 것인지 구상하고 접근해야함.
탐색방식: recursive call을 이용하여 각 노드에서 min 함수로 왼쪽 아래쪽 경로중 최소값+grid[m][n]을 return하는 방식으로 구현하고 
m,n 에 관한 메모리 맵을 만들어서 dp[m][n]을 기록해두고 -1이 아닐경우 return dp[m][n]으로 함수 중복 호출을 막는 방식으로 dp 구현

일단 전체탐색 알고리즘 구현하고 dp를 적용해도 되지만 dp 적용이 쉽지 않을 수 있음. 
*/

class Solution {
public:
    int** dp;
    int minPathSum(vector<vector<int> > &grid) {
        dp = new int*[grid.size()]; //for dp, save min value
        for(int i=0; i<grid.size() ; i++) {
           dp[i] = new int[grid[i].size()];
           memset(dp[i], -1, sizeof(int)*grid[i].size()); //filled with negative
        }
        
        return findPath(grid, 0, 0);
    }
    
    int findPath(vector<vector<int>> &grid, int m, int n) {
        if(m < grid.size()-1 && n < grid[m].size()-1) {
            if(dp[m][n] == -1) {
                dp[m][n] = grid[m][n] + min( findPath(grid, m+1, n) , findPath(grid, m, n+1));
            }
            
            return dp[m][n];
        } else if(m == grid.size()-1 && n < grid[m].size()-1) {
            if(dp[m][n] == -1) {
                dp[m][n] = grid[m][n] + findPath(grid, m, n+1);
            } 
            
            return dp[m][n];
        } else if(n == grid[m].size()-1 && m < grid.size()-1) {
            if(dp[m][n] == -1) {
                dp[m][n] = grid[m][n] + findPath(grid, m+1, n);
            } 
            
            return dp[m][n];
        } else { //base case
            if(dp[m][n] == -1) {
                dp[m][n] = grid[m][n];
            }    
            
            return dp[m][n];    
        }
    }
};