最小路径和---dp

思路这道题目和上一道题目很像复习一下动态规划的宗旨将大问题拆分成一个一个小问题然后将小问题的答案记录下来这时候我们基本可以得到小问题的dp[i]式子的含义。然后我们再去思考由小问题如何一步一步推导出大问题这时候状态转移方程就出来了。题目要求的是找出从左上角到右下角使得路径上的数字最小。那么dp[i][j]就是在当前位置上 路径经过的最小值。然后和上道题目一样我们需要处理一下边界值。先写出一版代码class Solution { public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; int[][] dp new int[1000][1000]; dp[0][0] grid[0][0]; for(int i 0;i m;i ){ for(int j 0;j n;j ){ if(i 0 j 0){ dp[i][j] grid[0][0]; } else if(j 0){ dp[i][j] dp[i - 1][j]grid[i][j]; } else if(i 0 ){ dp[i][j] dp[i][j - 1]grid[i][j]; } else{ dp[i][j] Math.min(dp[i - 1][j],dp[i][j - 1]) grid[i][j]; } } } return dp[m - 1][n - 1]; } }很幸运直接一遍过