题目描述
给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。 请你返回非零偏移下降路径数字和的最小值。
Example 1:
输入：arr = [[1,2,3],[4,5,6],[7,8,9]] 输出：13 解释： 所有非零偏移下降路径包括： [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] 下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
Constraints:
- 1 <= arr.length == arr[i].length <= 200
- -99 <= arr[i][j] <= 99
解题思路
- 给定了限制条件，某行某列，不能由上一行的列进行转化
- 可以暴搜，枚举一个最小值
C++代码
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
vector<vector<int>> dp(matrix.size(), vector<int>(matrix.size(), 0));
for(int i = 0; i < matrix[0].size(); i++){
dp[0][i] = matrix[0][i];
}
for(int i = 1; i < matrix.size(); i++){
for(int j = 0; j < matrix[0].size(); j++){
int val = matrix[i][j];
dp[i][j] = INT_MAX;
for(int k = 0; k < matrix[0].size(); k++){
if(j != k){
dp[i][j] = min(dp[i][j], dp[i - 1][k] + val);
}
}
}
}
int res = INT_MAX;
for(int i = 0; i < matrix[0].size(); i++){
res = min(res, dp[matrix.size() - 1][i]);
}
return res;
}
};
