首页 > 其他分享 >【DP】LeetCode 64. 最小路径和

【DP】LeetCode 64. 最小路径和

时间:2023-04-02 14:00:29浏览次数:53  
标签:int ++ length grid DP 64 LeetCode dp

题目链接

64. 最小路径和

思路

分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律

表示状态

假设到了右下角,考虑一下我们要存储的信息

  • 走到最后坐标的最小步数
  • 当前坐标的信息,用来判断是否走到了右下角

很容易联想到使用二维数组 dp[i][j] 来表示在坐标 \((i,j)\) 处的最小步数。

找状态转移方程

因为只能往下或者往右走并且

\[dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] \]

边界处理

我们只需要处理第一行和第一列就行。

第一行处理为

dp[0][i] =  i == 0 ? grid[0][i] : grid[0][i] + dp[0][i - 1];

第一列处理为

dp[i][0] =  i == 0 ? grid[i][0] : grid[i][0] + dp[i - 1][0];

代码

class Solution {
    public int minPathSum(int[][] grid) {
        // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        int[][] dp = new int[grid.length][grid[0].length];
        for(int i = 0; i < dp[0].length; i++){
            dp[0][i] =  i == 0 ? grid[0][i] : grid[0][i] + dp[0][i - 1];
        }
        for(int i = 0; i < dp.length; i++){
            dp[i][0] =  i == 0 ? grid[i][0] : grid[i][0] + dp[i - 1][0];
        }

        for(int i = 1; i < grid.length; i++){
            for(int j = 1; j < grid[i].length; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[grid.length - 1][grid[0].length - 1];
    }
}

标签:int,++,length,grid,DP,64,LeetCode,dp
From: https://www.cnblogs.com/shixuanliu/p/17280369.html

相关文章

  • 【DP】LeetCode 70. 爬楼梯
    题目链接70.爬楼梯思路分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律表示状态假设走到了最后一层台阶,考虑一下我们要存储的信息:走到这最后一层台阶的方法数当前台阶数,用于判断是否走到了最后一层台阶这时候......
  • mingw64 + nvim + coc.nvim + nvim-dap : C++ windows - 01
    目标用做C++编译器尽量不要扩展其它功能python是避免不了,所以才安装的。1.1下载安装https://mirror.tuna.tsinghua.edu.cn/msys2/distrib/msys2-x86_64-latest.exe安装路径:C:\gnu\msys641.2mingw64.exe使用这个:C:\gnu\msys64\mingw64.exe1.3安装程序:pac......
  • mingw64 + nvim + coc.nvim + nvim-dap : C++ windows - 02
    2.1命令行工具https://github.com/sharkdp/fdhttps://github.com/junegunn/fzfhttps://github.com/BurntSushi/ripgrephttps://github.com/tree-sitter/tree-sitterC:\gnu\cli\fd.exeC:\gnu\cli\fzf.exeC:\gnu\cli\rg.exeC:\gnu\cli\tree-sitter.exe添加到path......
  • mingw64 + nvim + coc.nvim + nvim-dap : C++ windows - 03
    3.1cclshttps://github.com/MaskRay/ccls/wiki/Build在msys中:pacman-S--noconfirmmingw-w64-x86_64-clangmingw-w64-x86_64-clang-tools-extramingw64/mingw-w64-x86_64-pollymingw-w64-x86_64-cmakemingw-w64-x86_64-jqmingw-w64-x86_64-ninjamingw-w64-x86_64-n......
  • mingw64 + nvim + coc.nvim + nvim-dap : C++ windows - 04
    4.1init.vim将init.vim放置到下面:echostdpath('config')~\AppData\Local\nvim4.2plughttps://github.com/junegunn/vim-plug将plug.vim放置到下面~\AppData\Local\nvim-data\site\autoload4.3:PlugInstall4.3.1网络问题gitproxy4.3.2process4.3......
  • mingw64 + nvim + coc.nvim + nvim-dap : C++ windows - 05
    PSC:\Users\dev\Desktop\cpp>cd.\build\PSC:\Users\dev\Desktop\cpp\build>cmake..-DCMAKE_BUILD_TYPE=Debug--Buildingfor:Ninja--TheCcompileridentificationisGNU12.2.0--TheCXXcompileridentificationisGNU12.2.0--Detect......
  • [LeetCode] 1338. Reduce Array Size to The Half 数组大小减半
    Youaregivenanintegerarray arr.Youcanchooseasetofintegersandremovealltheoccurrencesoftheseintegersinthearray.Return theminimumsizeofthesetsothat atleast halfoftheintegersofthearrayareremoved.Example1:Input:arr=......
  • Leetcode(剑指offer专项训练)——DP专项(4)
    加减的目标值给定一个正整数数组nums和一个整数target。向数组中的每个整数前添加 '+'或'-',然后串联起所有整数,可以构造一个表达式:例如,nums=[2,1],可以在2之前添加'+',在1之前添加'-',然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算......
  • 代码随想录Day17-Leetcode110.平衡二叉树,257. 二叉树的所有路径,404.左叶子之和
    110.平衡二叉树题目链接:https://leetcode.cn/problems/balanced-binary-tree/一个显然但似乎不太高效的方法是:通过递归获取左右子树高度,判断差;然后递归判断左右结点;那么一个显然的改进就是后序遍历/***Definitionforabinarytreenode.*functionTreeNode(val......
  • linux操作系统实验四-以time/gettimeofday系统调用为例分析ARM64 Linux 5.4.34
    一、搭配环境(1)安装编译工具sudoapt-getinstallgcc-aarch64-linux-gnusudoapt-getinstalllibncurses5-dev build-essentialgitbisonflexlibssl-dev(2)制作根文件系统wget https://busybox.net/downloads/busybox-1.33.1.tar.bz2tar-xjfbusybox-1.33.1.tar.bz2......