算法
February 4, 2019

LeetCode-Minimum Falling Path Sum

Minimum Falling Path Sum

题目描述

本题目链接：931. Minimum Falling Path Sum

Given a square array of integers A, we want the minimum sum of a falling paththrough A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row’s choice must be in a column that is different from the previous row’s column by at most one.

题目的意思是在一个给定的二维方格中，从上往下走。列方向每次只走一步，行方向上最多只能跨越一个单元格。即就是只能向正下方，左下方，右下方行进。每个方格都有一个值，目标是走到最后一行的路径中包含的值之和最小。

问题分析

还是使用动态规划，而动态规划的重中之重就是建立递推关系。

显然，对于第一行，我们选择最小的数进行开始；

然后，对于后面的，我们每次只要选择正下方，左下方，右下方中最小的数即可。

递推公式为：dp[i][j] = dp[i-1][j] + min(A[i][j-1], A[i][j], A[i][j+1])（注意对数组越界的处理）

C++实现

使用A当做dp数组，这样可以节省空间，但是我觉得对输入参数直接进行了修改，这样不是很好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minFallingPathSum(vector<vector<int>> &A) {
        for (auto i = 1; i < A.size(); ++i) {
            for (auto j = 0; j < A.size(); ++j) {
                A[i][j] +=
                        min({A[i - 1][max(0, j - 1)],
                             A[i - 1][j],
                             A[i - 1][min(static_cast<int>(A.size() - 1), j + 1)]});
            }

        }
        return *min_element(A.back().begin(), A.back().end());
    }
};

Scala实现

Scala版本的对输入参数A保持不变，但是这仍然不是纯函数的实现。如果有朋友有纯函数实现的方案，请不吝赐教！

1
2
3
4
5
6
7
8
9
10
11
12
object Solution {
  def minFallingPathSum(A: Array[Array[Int]]): Int = {
    val dp = A.clone()
    for (i <- 1 until dp.length; j <- dp.indices) {
      dp(i)(j) += List(
        dp(i - 1)(math.max(0, j - 1)),
        dp(i - 1)(j),
        dp(i - 1)(math.min(dp.length - 1, j + 1))).min
    }
    dp.last.min
  }
}