LeetCode Day29 Dynamic Programming Part 2

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28
Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100
Original Page

We can use this handwritten array simulation to explore the pattern (by the way, forgive my terrible handwriting).

    public int uniquePaths(int m, int n) {
        if(n<=1 || m<=1){
            return 1;
        }
        int dp[][] = new int[m+1][n+1];
        dp[0][1] = 1;
        for(int i=1; i<m+1; i++){
            for(int j=1; j<n+1; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];

    }

dp[0][1] = 1; for this code, actually it does not matter whether we use dp[1][0] = 1 or dp[0][1] = 1, because we want to match the index to m and n, we extend one more row and column when we init the array see: int dp[][] = new int[m+1][n+1];

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[][] dp = new int[row][col];

        boolean isBlocked = false;
        for(int i=0; i<row; i++){
            if(obstacleGrid[i][0]==1){
                isBlocked = true;
            }
                dp[i][0] = isBlocked ? 0 : 1;
        }

        isBlocked = false;
        for(int i=0; i<col; i++){

            if(obstacleGrid[0][i]==1){
                isBlocked = true;
            }
                dp[0][i] = isBlocked ? 0 : 1;
        }

        for(int i=1; i<row; i++){
            for(int j=1; j<col; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[row-1][col-1];  
    }

There is nothing especially hard to realize, we only need to consider the blocked thing but it is easy to think, which implies that when there is a blocked one, the grid that is left or down to the blocked one can not be reached through this direction. (the A grid's left grid is a blocked one, we can not from A's left moving to A, we can only find the up route, and this logic work for up as well)

343. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

2 <= n <= 58
Original Page

    public int integerBreak(int n) {
        if(n<=2){
            return 1;
        }
        //init
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 1;
        //logic
        for(int i=3; i<=n; i++){
            for(int num=1; num<i; num++){
                dp[i] = Math.max(
                    Math.max(num * (i - num), dp[i]),
                    num * dp[i - num]);

            }
        }

        // Arrays.stream(dp).forEach(System.out::println);
        return dp[dp.length-1];
    }