LeetCode 931 Minimum Falling Path Sum

动态规划问题 2022-02-14 21:14:14 2022-02-14 21:14:14 217 次浏览

概述

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;
    }
};

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