C++刷leetcode（931. 下降路径最小和）【动态规划】
本帖最后由 糖逗 于 2020-5-8 23:05 编辑题目描述：
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例：
输入：[,,]
输出：12
解释：
可能的下降路径有：
, , , ,
, , , , , ,
, , , ,
和最小的下降路径是 ，所以答案是 12。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-falling-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& A) {
int len1 = A.size(), len2 = A.size();
vector<vector<int> > dp(len1, vector<int>(len2, 0));
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(i == 0){
dp = A;
}else if(j == len2-1){
dp = min(dp, dp) + A;
}else if(j == 0){
dp = min(dp, dp)+ A;
}else{
dp = min(dp, dp);
dp = min(dp, dp) + A;
}
}
}
return *min_element(dp.begin(), dp.end());
}
};
页:
[1]