6 line Java DP solution 1ms


  • 0
    _
    
    public class Solution {
        
        
        // https://leetcode.com/problems/unique-paths/
            
        /*
        
        A robot is located at the top-left corner of a m x n grid 
        (marked 'Start' in the diagram below).
    
        The robot can only move either down or right at any point in time. 
        The robot is trying to reach the bottom-right corner of the grid 
        (marked 'Finish' in the diagram below).
    
        How many possible unique paths are there?
        
        
        +---+---+---+---+---+---+---+---+
        |ROB|   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+
        |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+
        |   |   |   |   |   |   |   |end|
        +---+---+---+---+---+---+---+---+
        
        
        */
        
        
        
        
        
        /*
        
        // https://discuss.leetcode.com/topic/5623
        // java-dp-solution-with-complexity-o-n-m
        
        The assumptions are:
    
            - When (n==0||m==0) the function always returns 1 since the robot
              can't go left or up.
        
            - For all other cells. The result = uniquePaths(m-1,n) + uniquePaths(m,n-1)
        
        Therefore I populated the edges with 1 first and use DP to get the full 2-D array.
        
        */
        
        /*
            
            +----+----+----+----+----+----+----+----+
            | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
            +----+----+----+----+----+----+----+----+
            | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  |
            +----+----+----+----+----+----+----+----+
            | 1  | 3  | 6  | 10 | 15 | 21 | 28 | 36 |
            +----+----+----+----+----+----+----+----+
            | 1  | 4  | 10 | 20 | 35 | 56 | 84 |120 |
            +----+----+----+----+----+----+----+----+
        
        */
        
        /*
        public int uniquePaths(int m, int n) {
            int[][] map = new int[m][n];
            
            for(int i = 0; i < m; i++){
                map[i][0] = 1;
            }
            
            for(int j = 0; j < n; j++){
                map[0][j] = 1;
            }
            
            for(int i = 1; i < m; i++){
                for(int j = 1; j < n; j++){
                    map[i][j] = map[i-1][j] + map[i][j-1];
                }
            }
            
            return map[m-1][n-1]; // the finish star.
        }
        */
        
        public int uniquePaths(int m, int n) {
            int[]dp = new int[n];
            dp[0] = 1;
            for(int i = 0; i < m; i++)
                for(int j = 1; j < n; j++)
                    dp[j] = dp[j] + dp[j-1];
            return dp[n-1]; // the finish star.
        }
        
        
        
    
    }
    
    
    

Log in to reply
 

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