Minimum Falling Path Sum

题目链接：题面

这题，我的思路是，类似于八皇后那样，用回溯的方法解决，想了好久的递归函数（我实在是太菜了），如下：

 1 private int dfs(int row, int col, int[][] a) {
 2         int n = a.length;
 3         if (row >= 0 && row < n && col >= 0 && col < n) {
 4             int left = dfs(row+1, col-1, a) + a[row][col];
 5             int mid = dfs(row+1, col, a) + a[row][col];
 6             int right = dfs(row+1, col+1, a) + a[row][col];
 7             return getMin(left, mid, right);
 8         } else if (row >= n) {
 9             return 0;
10         } 
11         return 105;
12 }

这个dfs函数的功能呢，就是我每遍历到一个矩阵中的数，然后判断这个位置合不合理，如果合理，我就从这个位置开始dfs,判断这个位置下面的三个位置，然后把这个最小路径和给弄上来；如果恰好遍历到了最后一行，那么根据这种写法，只能返回0；否则，返回一个比较大的数（特别注意这里不能是Integer.MIN_VALUE）,我就吃了很多亏，因为你这里返回一个最大数，到了递归的上一层，还需要加上a[row][col],那么这个数最终什么样就不得而知了，但肯定会影响结果。

然后，因为开始位置是在第一行里面随机挑选的，因此我最终只需要遍历第一行就行了，选出每个位置的最小值，就是我们要的答案。

1 public int minFallingPathSum(int[][] matrix) {
2         int n = matrix.length;
3         int ans = Integer.MAX_VALUE;
4         for (int j = 0; j < n; ++j) {
5             int temp = dfs(0, j, matrix);
6             ans = Math.min(ans, temp);
7         }
8         return ans;
9 }

这样就行了。

后来拿去一提交，就emo了。。。感觉不对啊，为什么转了那么久的圈圈，还没有出来结果呢？

啪！超时了。。。我敲！

后来一看题解，其实这题可以用动态规划来写。

我们定义一个二位dp,如dp[i][j],这个就表示到达坐标(i,j)的最小路径和。然后，我们只需要注意几点情况：1.对于第一行的数据，最小路径和就是其本身，这一点无可厚非；2.对于所有第一列和最后一列的数据，我们只有两个可能的来源需要考虑，例如对于第一列的数据，我们只需考虑这个数据上一行同列的数据和上一行右边一列的数据，这一点注意清楚就好了；3.边界条件考虑清楚了，那对于其他的数据就有三个来源方向考虑，这个就很简单了，根据题目意思来即可。

核心代码：

 1 public int minFallingPathSum(int[][] matrix) {
 2         int row = matrix.length;
 3         int col = matrix[0].length;
 4         int[][] dp = new int[row][col];
 5         for (int i = 0; i < row; ++i) {
 6             for (int j = 0; j < col; ++j) {
 7                 if (i == 0) {
 8                     dp[i][j] = matrix[i][j];
 9                 } else if (j == 0) {
10                     dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j+1]) + matrix[i][j];
11                 } else if (j == col - 1) {
12                     dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + matrix[i][j];
13                 } else {
14                     dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i-1][j+1]) + matrix[i][j];
15                 }
16             }
17         }
18         int ans = Integer.MAX_VALUE;
19         for (int j = 0; j < col; ++j) {
20             ans = Math.min(ans, dp[row-1][j]);
21         }
22         return ans;
23     }

顺便提一句，本人在重写代码的时候，除了i==0的情况，其他三种情况全忘记加matrix[i][j]了[QAQ].

下面再来一道题，相当于是这道题的变形：

题面

这道题呢，采用跟上一道题几乎一模一样的解法：

 1 public int minimumTotal(List> triangle) {
 2         int n = triangle.size();
 3         int[][] dp = new int[n][n];
 4         int temp = 1;
 5         for (int i = 0; i < n; ++i) {
 6             for (int j = 0; j < temp; ++j) {
 7                 if (i == 0) {
 8                     dp[i][j] = triangle.get(i).get(i);
 9                 } else if (j == 0) {
10                     dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
11                 } else if (j == temp - 1) {
12                     dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
13                 } else {
14                     dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle.get(i).get(j);
15                 }
16             }
17             ++temp;
18         }
19         int ans = Integer.MAX_VALUE;
20         for (int j = 0; j < temp; ++j) {
21             ans = Math.min(ans, dp[n-1][j]);
22         }
23         return ans;
24     }

无非就是对于列数的处理与上一道题不同，直接开个新变量，每次列遍历完，在遍历下一行之前让列数加1就行了，其他几乎没怎么变，边界条件也跟上一道题一样。

但是你会发现上面的代码有问题，问题出在哪呢？

就出在用来遍历列而开的一个临时变量temp上。试想一下，这个temp初始值是1，每次遍历完一行就加了1，到最后全部遍历结束时，是不是这个temp是比triangle的size还要大的？大多少呢？只大了1.然后我们再去寻找答案的时候，你把temp作为最终j不能超过的那个数，肯定会数组越界的。

我们在最后把这个temp变成n就好了。

其实根本不用这么麻烦，本人只是编程技术太不熟练，才搞了这么多幺蛾子出来，你完全可以采用for (int j = 0; j < i; ++j)这样的写法，不用专门搞一个临时变量出来。