Dynamic Programming Solution in Go


  • 0
    J
    package main
    
    func minPathSum(grid [][]int) int {
    	if grid == nil || len(grid) == 0 || len(grid[0]) == 0 {
    		return 0
    	}
    	m := len(grid)
    	n := len(grid[0])
    	dp := make([][]int, m)
    	for i := range dp {
    		dp[i] = make([]int, n)
    	}
    	dp[0][0] = grid[0][0]
    
    	for i := 1; i < n; i++ {
    		dp[0][i] = dp[0][i-1] + grid[0][i]
    	}
    	for i := 1; i < m; i++ {
    		dp[i][0] = dp[i-1][0] + grid[i][0]
    	}
    
    	for i := 1; i < m; i++ {
    		for j := 1; j < n; j++ {
    			if dp[i-1][j]+grid[i][j] > dp[i][j-1]+grid[i][j] {
    				dp[i][j] = dp[i][j-1] + grid[i][j]
    			} else {
    				dp[i][j] = dp[i-1][j] + grid[i][j]
    			}
    
    		}
    	}
    	return dp[m-1][n-1]
    
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.