LeetCode 931 Minimum Falling Path Sum

概述

https://leetcode.com/problems/minimum-falling-path-sum/

极值问题，直接上动态规划

动态规划法

1. base case：
2. 状态：出发点（行列）
3. 选择：左下，正下，还是右下
4. dp 函数 / 数组的定义：dp[i][j] = 从 i 行 j 列开始下降的最少和

代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        vector<vector<int>> dp = matrix;
        for (int r = matrix.size() - 2; r >= 0; r --) {
            for (int c = 0; c < matrix[0].size(); c ++) {
                int minV = dp[r+1][c];
                if (c != 0) minV = min(minV, dp[r+1][c-1]);
                if (c != matrix[0].size() - 1) minV = min(minV, dp[r+1][c+1]);
                dp[r][c] = matrix[r][c] + minV;
            }
        }
        int ans = INT_MAX;
        for (auto n : dp[0]) ans = min(ans, n);
        return ans;
    }
};

Links: leetcode-931-minimum-falling-path-sum

未经允许，禁止转载，本文源站链接：https://iamazing.cn/