Dynamic rules - array compression optimization

First, let's look at a simple and classic dynamic programming problem

link ： Minimum path sum

Ideas

Recurrence of violence

General dynamic programming problems , First use violence recursion to sort out ideas , Relatively easy . Then, according to the recursive equation of violent recursion, it is changed into the dynamic programming equation .

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        if(grid==null||grid.length==0){
    
            return 0;
        }
        return process(0,0,grid);
    }

	// The meaning of the recursive equation indicates , When it comes to the point (i,j) When in position , Change the shortest path from the point to the point in the lower left corner and 
	public int process(int i,int j,int[][] grid){
    
        if(i> grid.length-1){
    
            return Integer.MAX_VALUE/2;
        }
        if(j> grid[0].length-1){
    
            return Integer.MAX_VALUE/2;
        }
        if(i== grid.length-1&&j==grid[0].length-1){
    
            return grid[i][j];
        }
        int p1=grid[i][j]+process(i+1,j,grid);
        int p2=grid[i][j]+process(i,j+1,grid);
        return Math.min(p1,p2);
    }

Violence recurs to dynamic programming

Look at the parameters of recursive equations in violent recursion , There are two variable parameters , There is an invariant parameter , Two of these variable parameters can be regarded as dp The table is a two-dimensional array , Then change to dynamic programming according to the dependency

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        if(grid==null||grid.length==0){
    
            return 0;
        }
        if(grid.length==1&&grid[0].length==1){
    
            return grid[0][0];
        }
        int lenX=grid.length;
        int lenY= grid[0].length;

        int[][] dp=new int[lenX][lenY];
        dp[lenX-1][lenY-1]=grid[lenX-1][lenY-1];
        for(int i=lenX-1;i>=0;i--){
    
            for(int j=lenY-1; j>=0; j--){
    
                dp[i][j]=Math.min(grid[i][j]+get(dp,i+1,j,grid), grid[i][j]+get(dp,i,j+1,grid));
            }
        }
        return dp[0][0];
    }
    public int get(int[][] dp,int i,int j,int[][] grid){
    
        int lenX=dp.length;
        int lenY=dp[0].length;
        if(i>lenX-1){
    
            return Integer.MAX_VALUE/2;
        }
        if(j>lenY-1){
    
            return Integer.MAX_VALUE / 2;
        }
        if(i==lenX-1&&j==lenY-1){
    
            return grid[i][j];
        }
        return dp[i][j];
    }}

A two-dimensional dp Compress the array to one dimension dp

From the above we can see , The current point depends on the left point and the lower point , This is a , As long as dependencies like this depend on adjacent points , You can use array compression for optimization .

public int minPathSum(int[][] grid) {
    
        if(grid==null||grid.length==0){
    
            return 0;
        }
        int lenX=grid.length;
        int lenY= grid[0].length;


        int[] dp=new int[lenY];
        dp[lenY-1]=grid[lenX-1][lenY-1];
        for(int i=lenY-2;i>=0;i--){
    
            dp[i]=dp[i+1]+grid[lenX-1][i];
        }
        for(int i=lenX-2;i>=0;i--){
    
            dp[lenY-1]+=grid[i][lenY-1];
            for(int j=lenY-2;j>=0;j--){
    
                dp[j]=Math.min(dp[j],dp[j+1])+grid[i][j];
            }
        }
        return dp[0];
    }

Convert a two-dimensional array into a one-dimensional array .