无忧网站建设公司,网页制作模板蛋糕,购物网站案例,wordpress更改主题名称文章目录1. 题目2. 动态规划解题1. 题目
给定一个方形整数数组 A#xff0c;我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始#xff0c;并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例#xff1a;
输…
文章目录1. 题目2. 动态规划解题1. 题目
给定一个方形整数数组 A我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例
输入[[1,2,3],[4,5,6],[7,8,9]]
输出12解释
可能的下降路径有
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
和最小的下降路径是 [1,4,7]所以答案是 12。提示
1 A.length A[0].length 100
-100 A[i][j] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-falling-path-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 动态规划解题
这题很简单DP解题
状态表初始化数值INT_MAX状态表第一行就是数组本身从第二行开始每个格子可以接受他头顶的3个左中右状态的最小的过来状态方程如下 dp[i][j]A[i][j]min(dp[i−1][j−1],dp[i−1][j],dp[i−1][j1])dp[i][j] A[i][j]min(dp[i-1][j-1], \quad dp[i-1][j],\quad dp[i-1][j1])dp[i][j]A[i][j]min(dp[i−1][j−1],dp[i−1][j],dp[i−1][j1])为了方便处理边界状态表左右各加1列
class Solution {
public:int minFallingPathSum(vectorvectorint A) {const int N A.size();vectorvectorint dp(N,vectorint(N2,INT_MAX));int i, j, minSum INT_MAX;for(i 0; i N; i) dp[0][i1] A[0][i];//初始化第一行for(i 1; i N; i){for(j 1; j N1; j){ //注意加了两列后下标的错位dp[i][j] A[i][j-1]min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j1]);}}for(i 1; i N1; i)minSum min(minSum,dp[N-1][i]);//最后一行最小return minSum;}
};状态可以压缩观察到下一行状态只跟上一行状态有关所以只需要2行数组空间即可
class Solution {
public:int minFallingPathSum(vectorvectorint A) {const int N A.size();vectorint dp(N2,INT_MAX);vectorint temp(N2,INT_MAX);int i, j, minSum INT_MAX;for(i 0; i N; i) temp[i1] A[0][i];//初始化第一行for(i 1; i N; i){for(j 1; j N1; j){ //注意加了两列后下标的错位dp[j] A[i][j-1]min(min(temp[j-1],temp[j]),temp[j1]);}swap(dp,temp);}return *min_element(temp.begin(),temp.end());}
};
