39 ms c# DP solution, beats 100% c# submissions


  • 0
    P
    public class Solution {
    // inspired from the CC150 9.1
        public int UniquePaths(int m, int n) {
            //buld a matrix to cache the resolved solutions
            var mat = new int[m,n];
            return UniquePaths(m, n, mat);
        }
        
        public int UniquePaths(int m, int n, int[,] mat) {
            if (m <= 0 || n <= 0) {
                return 0;
            } else if (m == 1 && n == 1) {
                //recursion base condition
                return 1;
            }else if (mat[m - 1, n - 1] > 0) {
                return mat[m - 1, n - 1];
            } else {
                // main recursion, store result into the maxtrix
                mat[m - 1, n - 1] = UniquePaths(m - 1, n, mat) 
                   + UniquePaths(m, n - 1, mat);
                return mat[m - 1, n - 1];
            }
        }
    //hope it might help
    

    }


Log in to reply
 

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