[OJ.leetcode] minimum-path-sum

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

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

/* 초기 접근: 전수조사를 해야하는가->그렇다. 어떻게 가지치기 할 것인가-> 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]; } } };