LeetCode Day動態程式設計第 2 部分

62.獨特的路徑

m x n 網格上有一個機器人。機器人最初位於左上角（即 grid[0][0]）。機器人嘗試移動到右下角（即 grid[m - 1][n - 1]）。機器人在任何時間點只能向下或向右移動。

給定兩個整數 m 和 n，返回機器人到達右下角可能採取的唯一路徑的數量。

產生的測試案例的答案將小於或等於 2 * 109。

範例1：

輸入：m = 3，n = 7
輸出：28
範例2：

輸入：m = 3，n = 2
輸出：3
說明：從左上角開始，到達右下角一共有3種方式：

1. 右 ->向下->向下
2. 向下->向下->對了
3. 向下->右->向下

限制：

1 原始頁

我們可以使用這個手寫數組模擬來探索模式（順便原諒我糟糕的筆跡）。

    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;對於這段程式碼，實際上我們使用dp[1][0] = 1 還是dp[0][1] = 1 並不重要，因為我們想要將索引匹配到m 和n，我們再擴展一行並當我們初始化數組時看到的列： 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];  
    }

沒有什麼特別難實現的，我們只需要考慮被遮擋的東西就可以了，但是很容易想到，這意味著當有遮擋的時候，被遮擋的左邊或者下面的格子是不能被通過這個方向到達。 （A格子左邊的格子是被封鎖的，我們無法從A的左邊移動到A，只能找到向上的路線，這個邏輯也適用於向上）

343. 整數中斷

給定一個整數 n，將其分解為 k 個正整數之和，其中 k >= 2，並最大化這些整數的乘積。

返回您可以獲得的最大產品。

範例1：

輸入：n = 2
輸出：1
解釋：2 = 1 + 1, 1 × 1 = 1.
範例2：

輸入：n = 10
輸出：36
解釋：10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

限制：

2 原始頁

    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];
    }

以上是LeetCode Day動態程式設計第 2 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！