三角形的最小路径和---二维dp

这是一道非常经典的题目；

首先我们回顾一下如何得到dp的定义和dp的式子。

首先我们要明白动态规划的宗旨，动态规划是将大问题拆分成一个一个小问题，然后将小问题的答案记录下来，这时候我们应该可以定义出小问题的含义也就是dp[i]其中的i和dp代表什么。

然后我们需要推理大问题如何由小问题得到，这时候状态转移方程就产生了。

思路：拿到这道题没什么思路 我觉得dp[i][j]应该表示的是在当前位置上满足条件的最小的路径之和，

不要不自信，就是这样的。

那么想一下状态转方程应该怎么写，由题意我们知道，当前位置可以由上一行的第i个位置得到，也可以由上一行的第j - 1个位置得到，于是我们可以写出状态转移方程是，dp[i][j] = Math.min(dp[i - 1][j],dp[i - 1][j - 1]) + target[i][j];

写出来状态转移方程之后我们就要考虑边界的问题了

最左边那一列的数只能由上一行的第j个位置得到，最右边那一列的数只能由上一行的第 j- 1个位置得到。

于是我们不难写出代码：

class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int [][] dp = new int[300][300]; dp[0][0] = triangle.get(0).get(0); for(int i = 1;i < n;i++){ for(int j = 0;j <=i;j ++){ if(j == 0){ dp[i][j] = dp[i - 1][0] + triangle.get(i).get(j); } else if(j == i){ dp[i][j] = dp[i - 1][j -1] + triangle.get(i).get(j);//这里最开始写错了 }else{ dp[i][j] = Math.min(dp[i - 1][j - 1],dp[i -1][j]) + triangle.get(i).get(j); } } } int min = Integer.MAX_VALUE; for(int i = 0;i < n;i ++){ //这里不认真也写错了 if(dp[n - 1][i] < min){ min = dp[n - 1][i]; } System.out.println(dp[n - 1][i]); } return min; } }