二维动态规划题目（未完）

��     

     1.最小路径和（力扣LCR 99题）

        给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

        说明：一个机器人每次只能向下或者向右移动一步。

        方法一：暴力递归

    //暴力递归    public static int minPathSum(int[][] grid){        return f1(grid,grid.length-1,grid[0].length-1);    }    public static int f1(int[][] grid,int i,int j){        if(i==0 && j==0){            return grid[0][0];        }        int up=Integer.MAX_VALUE;//从上边的格子移动过来的        int left=Integer.MAX_VALUE;//从左边的格子移动过来的        if(i-1>=0){//判断不越界            up=f1(grid,i-1,j);        }        if(j-1>=0){//判断不越界            left=f1(grid,i,j-1);        }        return grid[i][j]+Math.min(up,left);    }

        暴力递归思路很清晰但是时间复杂度会非常高。提交也会超时。

        因为此暴力递归中，存在大量的重复计算，因此，时间复杂度比较差。

        方法二：记忆化递归

        带有记忆化的递归，也就是将每次的计算结果存入到一个结构中，每次发生重复计算时，直接从存数据的结构中取数据即可，由此可以减少大量的重复计算，时间复杂度有了较大的优化。

class Solution {    public static int minPathSum(int[][] grid){        int n=grid.length;        int m=grid[0].length;        int[][] dp=new int[n][m];        for(int i=0;i=0){//判断不越界                left=f2(grid,i,j-1,dp);            }            ans=grid[i][j]+Math.min(up,left);        }        dp[i][j]=ans;        return ans;    }}

        方法三：根据依赖关系推出

        每一个位置，只能从上或者左得到，只依赖上和左。

class Solution {   //非递归，按照依赖关系求解    public static int minPathSum(int[][] grid){        int n=grid.length;        int m=grid[0].length;        int[][] dp=new int[n][m];        dp[0][0]=grid[0][0];        for(int i=1;i