力扣labuladong一刷day61天动态规划最小下降路径

力扣labuladong一刷day61天动态规划最优子结构

一、931. 下降路径最小和

题目链接：https://leetcode.cn/problems/minimum-falling-path-sum/description/
如下图所示，求最小下降路径，定义dp[i][j]表示从最上面那行的任意位置抵达到nums[i][j]这个位置的最小路径和。根据题意每个位置只能从它上一行中的正上方的3个位置中得来，递推公式为dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])+nums[i][j]，因为是下降路径，遍历顺序自然是从上往下，从左往右，没啥限制每个节点都得遍历，时间复杂度为n2。可以不new新的dp数组，直接在nums上做运算，空间复杂度1。

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int len = matrix.length, max = Integer.MAX_VALUE;
        for (int i = 1; i  matrix.length; i++) {
            for (int j = 0; j  matrix.length; j++) {
                int left = j-1>=0 ? matrix[i-1][j-1]:max;
                int mid = matrix[i-1][j];
                int right = j+1len ? matrix[i-1][j+1]:max;
                matrix[i][j] = Math.min(Math.min(left, mid), right) + matrix[i][j];
            }
        }
        int min = Integer.MAX_VALUE;
     服务器托管网   for (int i = 0; i  len; i++) {
            min = Math.min(min, matrix[len-1][i]);
        }
        return min;
    }
服务器托管网}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: Nodejs 第二十一章（crypto）

密码学是计算机科学中的一个重要领域，它涉及到加密、解密、哈希函数和数字签名等技术。Node.js是一个流行的服务器端JavaScript运行环境，它提供了强大的密码学模块，使开发人员能够轻松地在其应用程序中实现各种密码学功能。本文将介绍密码学的基本概念，并探讨…