[Java] 64.Minimum Path Sum - LeetCode / Dynamic Programing(DP)

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

Minimum Path Sum - LeetCode

 
 

풀이

---

이차원배열 grid에서, 오른쪽, 아래로만 이동할 수 있을 때, 모든 숫자의 합을 최소화 하는 경로를 찾는 dp문제.
 
오른쪽, 아래로만 이동할 수 있으므로, i나 j가 0일때만 고려해주면 됐다.

class Solution{
	 
    public int minPathSum(int[][] grid) {
	        
	    for(int i=0; i<grid.length; i++) {
	    	for(int j=0; j<grid[i].length; j++) {	    		
	    		dp(grid, i, j);
	    	}
	    }
	    
	    return grid[grid.length-1][grid[0].length-1];
    	
	}
    
    public void dp(int[][] grid, int i, int j) {
    	if(i==0 && j==0) return;
    	else if(i==0) grid[i][j] += grid[i][j-1];
    	else if(j==0) grid[i][j] += grid[i-1][j];
    	else grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
    	
    }
}