Different approaches: DP+O(n) space and Recursion+Memoization


  • 0
    K

    DP:

        public int minPathSum(int[][] m) {
            for(int i=0; i<m.length; i++) {
                for(int j=0;j<m[0].length; j++) {
                    if(i == 0 && j == 0) m[i][j] = m[i][j];
                    else if(i == 0) m[0][j] += m[0][j-1];
                    else if(j == 0) m[i][0] += m[i-1][0];
                    else m[i][j] = Math.min(m[i][j-1] + m[i][j], m[i-1][j] + m[i][j]);
                }
            }
            return m[m.length-1][m[0].length-1];
        }
    

    Recursion with Memoization:

        public int minPathSum(int[][] m) {
            int[][] m1 = new int[m.length][m[0].length];
            minPathSum(m, m1, 0, 0, 0);
            return m1[m1.length-1][m[0].length-1];
        }
        
        private void minPathSum(int[][] m, int[][] m1, int r, int c, int sum) {
            if(r > m.length-1 || c > m[0].length-1) return;
            sum += m[r][c];
            if(m1[r][c] != 0 && sum > m1[r][c]) return;
            m1[r][c] = sum;
            minPathSum(m, m1, r+1, c, sum);
            minPathSum(m, m1, r, c+1, sum);
        }
    

    PS: Recursive solution fails with TimeLimitExceeded. A good indication of why DP outperforms Recursive solutions.


Log in to reply
 

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