【动态规划】 LCR 099. 最小路径和

2024-01-01 14:27:40

LCR 099. 最小路径和

解题思路

  • 采用动态规划的思路
  • 每次搜索都是向上或者向左进行搜索
  • dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值。
  • 同时(i,j)到(i - 1,j - 1)有两种方法,所以一定存在重叠子问题
  • 设置备忘录Memo存储dp过程中所有重叠子问题的解

class Solution {
    int[][] memo;// 备忘录


    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        memo = new int[m][n];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dp(grid,grid.length - 1,grid[0].length - 1);
    }

    int dp(int[][] grid,int i,int j){
        if(i == 0 && j == 0){
            return grid[0][0];
        }

        if(i < 0 || j < 0){
            return Integer.MAX_VALUE;
        }

        // 查找备忘录 有没有子问题的结果
        if(memo[i][j] != -1){
            return memo[i][j];
        }

        memo[i][j] = Math.min(dp(grid,i - 1,j),dp(grid,i,j - 1)) + grid[i][j];

        return memo[i][j];
    }
}

文章来源:https://blog.csdn.net/qq_44653420/article/details/135324120
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。