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数组，这样可以节省空间，但是我觉得对输入参数直接进行了修改，这样不是很好。
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保持不变，但是这仍然不是纯函数的实现。如果有朋友有纯函数实现的方案，请不吝赐教！
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
}
}