64. Minimum Path Sum

아마 기업에서 출제할 수 있는 가장 정석적인? dp문제가 아닐까 생각된다.

그렇게 쉽지도 어렵지도 않은? 적당한 난이도의 문제이다.

 

[메인 로직]

(i, j)에서는 dp[i][j-1]과 dp[i-1][j]와 각각 자신의 원래 값 grid[i][j]을 더한 것 중 더 작은 값을 dp값으로 저장해둔다.

 

class Solution {
public:
    int dp[201][201] = {0, };
    
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                dp[i][j] = INT_MAX;
            }
        }
        
        dp[0][0] = grid[0][0];
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i-1>=0){
                    dp[i][j] = min(dp[i][j], dp[i-1][j]+grid[i][j]);  
                }
                if(j-1>=0){
                    dp[i][j] = min(dp[i][j], dp[i][j-1]+grid[i][j]);
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};