DFS with Memorization


  • 0
    J

    when it comes to DP, I alwasy prefer to use Recursive + Memorization instead of the bottom up way. bcz it is more straight forward for me. I am wondering if it is good enough?

      Map<Turple, Long> map =new HashMap<Turple,Long>();
        class Turple{
            int i;
            int j;
            int k;
            public Turple(int i,int j, int k){
                this.i=i;
                this.j=j;
                this.k=k;
            }
            @Override
    		public int hashCode() {
    			final int prime = 31;
    			int result = 1;
    			result = prime * result + i;
    			result = prime * result + j;
    			result = prime * result + k;
    			return result;
    		}
    
    		@Override
    		public boolean equals(Object obj) {
    			if (this == obj)
    				return true;
    			if (obj == null)
    				return false;
    			if (getClass() != obj.getClass())
    				return false;
    			Turple other = (Turple) obj;
    			if (i != other.i)
    				return false;
    			if (j != other.j)
    				return false;
    			if (k != other.k)
    				return false;
    			return true;
    		}
                
        }
        public int findPaths(int m, int n, int N, int i, int j) {
            return (int)helper(m,n,N,i,j);
        }
        public long helper(int m, int n, int N, int i, int j) {
            long cnt=0;
            if(map.get(new Turple(i,j,N))!=null){
                return map.get(new Turple(i,j,N));
            }
            if(i<0||j<0||i>m-1||j>n-1) {
                cnt++;
                return cnt;
            }
            if(N<=0) return cnt;
            cnt=helper(m,n,N-1,i-1,j)+
            helper(m,n,N-1,i+1,j)+
            helper(m,n,N-1,i,j-1)+
            helper(m,n,N-1,i,j+1);
            cnt=cnt%1000000007;
            map.put(new Turple(i,j,N),cnt);
            return cnt;
        }
    
    

Log in to reply
 

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