6ms Java DP simple solution with comment


  • 0
    L
    public class Solution {
        public int uniquePaths(int m, int n) {
            if( m<1 || n <1) {
                return 0;
            }
            //Store the substructure result to avoid duplicate computation.
            Map<String /* ixj */, Integer> memo = new HashMap<String, Integer>();
            return subPaths(m-1, n-1, memo);
        }
    
    
        /**
         * Recursive call to get paths of sub-matrix
         */
        private int subPaths(int i, int j, Map<String, Integer> memo) {
            if( i==0 || j==0) {
                //NOTE: On the last row OR column, reaching to the target has ONLY ONE path .
                return 1;
            }
            String memoKey = i + "x" +j;
    
            if( memo.containsKey(memoKey)) {
                return memo.get(memoKey);
            } else {
                int paths = subPaths (i-1, j, memo) + subPaths (i, j-1, memo);
                memo.put(memoKey, paths);
                return paths;
            }
        }
    }
    

Log in to reply
 

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