64.最小路径和
64.最小路径和
题解
动态规划四要素
- 状态 State
灵感，创造力，存储小规模问题的结果 - 方程 Function
状态之间的联系，怎么通过小的状态，来算大的状态 - 初始化 Intialization
最极限的小状态是什么，起点 - 答案 Answer
最大的那个状态是什么，终点
state: dp[x][y]从起点走到 x,y 的最短路径
function: dp[x][y] = min(dp[x-1][y], dp[x][y-1]) + A[x][y]
intialize: dp[0][0] = A[0][0]
answer: dp[n-1][m-1]
代码
package main func minPathSum(grid [][]int) int { dp := make([][]int, len(grid)) for i := 0; i < len(grid); i++ { dp[i] = make([]int, len(grid[i])) copy(dp[i], grid[i]) } for i := 0; i < len(grid); i++ { for j := 0; j < len(grid[i]); j++ { if i == 0 && j == 0 { dp[i][j] = grid[i][j] } else if i == 0 { dp[i][j] = dp[i][j-1] + grid[i][j] } else if j == 0 { dp[i][j] = dp[i-1][j] + grid[i][j] } else { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] } } } return dp[len(grid)-1][len(dp[len(grid)-1])-1] } func min(a, b int) int { if a > b { return b } return a }
