LeetCode Day動的プログラミング パート 2

62. ユニークなパス

m x n のグリッド上にロボットがあります。ロボットは最初は左上隅 (つまり、grid[0][0]) に配置されます。ロボットは右下隅 (つまり、grid[m - 1][n - 1]) に移動しようとします。ロボットは、いかなる時点でも下または右のいずれかにしか移動できません。

2 つの整数 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 に一致させたいので、もう 1 行拡張し、配列を初期化するときの列を参照してください: 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 中国語 Web サイトの他の関連記事を参照してください。