LeetCode DayDynamic Programming Teil 2

62. Einzigartige Wege

Auf einem mxn-Raster befindet sich ein Roboter. Der Roboter befindet sich zunächst in der oberen linken Ecke (d. h. Grid[0][0]). Der Roboter versucht, sich in die untere rechte Ecke zu bewegen (d. h. Grid[m – 1][n – 1]). Der Roboter kann sich zu jedem Zeitpunkt nur entweder nach unten oder nach rechts bewegen.

Geben Sie anhand der beiden Ganzzahlen m und n die Anzahl der möglichen eindeutigen Pfade zurück, die der Roboter nehmen kann, um die untere rechte Ecke zu erreichen.

Die Testfälle werden so generiert, dass die Antwort kleiner oder gleich 2 * 109 ist.

Beispiel 1:

Eingabe: m = 3, n = 7
Ausgabe: 28
Beispiel 2:

Eingabe: m = 3, n = 2
Ausgabe: 3
Erläuterung: Von der oberen linken Ecke gibt es insgesamt 3 Möglichkeiten, die untere rechte Ecke zu erreichen:

1. Rechts -> Unten -> Runter
2. Runter -> Unten -> Richtig
3. Runter -> Rechts -> Runter

Einschränkungen:

1 <= m, n <= 100
Originalseite

Wir können diese handschriftliche Array-Simulation verwenden, um das Muster zu erkunden (verzeihen Sie übrigens meine schreckliche Handschrift).

    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; Für diesen Code spielt es eigentlich keine Rolle, ob wir dp[1][0] = 1 oder dp[0][1] = 1 verwenden, da wir den Index an m und n anpassen möchten, erweitern wir eine weitere Zeile und Spalte, wenn wir das Array initialisieren, siehe: 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];  
    }

Es gibt nichts besonders Schwieriges zu erkennen, wir müssen nur die blockierte Sache berücksichtigen, aber es ist leicht zu denken, was impliziert, dass, wenn es eine blockierte Sache gibt, das Gitter, das übrig bleibt oder bis zu der blockierten Sache reicht, nicht sein kann durch diese Richtung erreicht. (Das linke Gitter des A-Gitters ist blockiert, wir können uns nicht von A nach links bewegen, wir können nur die Aufwärtsroute finden, und diese Logik funktioniert auch für Aufwärts)

343. Ganzzahliger Bruch

Breiten Sie eine gegebene ganze Zahl n in die Summe von k positiven ganzen Zahlen auf, wobei k >= 2, und maximieren Sie das Produkt dieser ganzen Zahlen.

Geben Sie das maximale Produkt zurück, das Sie erhalten können.

Beispiel 1:

Eingabe: n = 2
Ausgabe: 1
Erklärung: 2 = 1 + 1, 1 × 1 = 1.
Beispiel 2:

Eingabe: n = 10
Ausgabe: 36
Erklärung: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Einschränkungen:

2 <= n <= 58
Originalseite

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

Das obige ist der detaillierte Inhalt vonLeetCode DayDynamic Programming Teil 2. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!