DP counter-intutive


  • 0
    A
    import java.util.*;
    class Solution {
        
        int m,n;
        int mod=(int)Math.pow(10,9)+7;
        HashMap<String,Integer> memo;
    
        public int findPaths(int m, int n, int N, int i, int j) {
     	       memo=new HashMap();
     	       this.m=m;
     	       this.n=n;
     	       int init[]=crd(i,j);
     	       return dp(init,N)%mod;
     	       
        }
        
        // takes in the current state 
        int dp(int[] c,int step){
        	String key=c[0]+":"+c[1]+":"+step;
        	if(memo.containsKey(key)) return memo.get(key)%mod;
        	if(oob(c[0],c[1])) return 1;
        	if(step<=0) return 0;
        	int res=0;
        	int x=c[0];
        	int y=c[1];
        	int[] l=crd(x-1,y);
        	int[] r=crd(x+1,y);
        	int[] u=crd(x,y-1);
        	int[] d=crd(x,y+1);
        	res=res%mod+dp(l,step-1)%mod;
        	res=res%mod+dp(r,step-1)%mod;
        	res=res%mod+dp(u,step-1)%mod;
        	res=res%mod+dp(d,step-1)%mod;
        	memo.put(key,res%mod);
        	//System.out.println(key+" "+res);
        	return res;
        }
    
       // pair x,y in an array
        int[] crd(int i,int j){
        	return new int[]{i,j};
        }
    
       // if current coords are out of bounds  o.o.b
       boolean oob(int i,int j){
        	if(i<0 || i>=m) return true;
        	if(j<0 || j>=n) return true;
        	return false;
        }
    
    }
    

    A dp solution is basically doing computation for a given state. the state of dp is the input that it takes to process, in this case, we take the coords and steps left to reach oob and from this, we spread to left, right, up and down. the trick part in this problem, or every dp problem, is identification of state.initially, I mistook the coordinates only as the part of a state, but every coordinate it has its own importance taken in account the number of steps it has left to proceed, what I mean is: lets input 2,2,6,0,0, here 0,0 with 4 steps will have a different result than 0,0 with 2 steps, so steps are affecting the result for every coordinate. once it is figured, all you have to do it is memoize the result for every key and that is your complete solution.

    Here is the result for exemplary input:
    key=> x-coord:y-coord:steps_left
    output= key result

    1:0:1 2
    0:1:1 2
    0:0:2 6
    1:1:2 6
    1:0:3 14
    0:1:3 14
    0:0:4 30
    1:1:4 30
    1:0:5 62
    0:1:5 62
    0:0:6 126
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.