Programmation dynamique LeetCode Day, partie 2

62. Chemins uniques

Il y a un robot sur une grille m x n. Le robot est initialement situé dans le coin supérieur gauche (c'est-à-dire, grille[0][0]). Le robot essaie de se déplacer vers le coin inférieur droit (c'est-à-dire grille[m - 1][n - 1]). Le robot ne peut se déplacer que vers le bas ou vers la droite à tout moment.

Étant donné les deux entiers m et n, renvoie le nombre de chemins uniques possibles que le robot peut emprunter pour atteindre le coin inférieur droit.

Les cas de tests sont générés pour que la réponse soit inférieure ou égale à 2*109.

Exemple 1 :

Entrée : m = 3, n = 7
Sortie : 28
Exemple 2 :

Entrée : m = 3, n = 2
Sortie : 3
Explication : Depuis le coin supérieur gauche, il existe au total 3 façons d'atteindre le coin inférieur droit :

1. Droite -> Vers le bas -> En bas
2. Bas -> Bas -> C'est vrai
3. Bas -> Droite -> En bas

Contraintes :

1 <= m, n <= 100
Page originale

Nous pouvons utiliser cette simulation de tableau manuscrit pour explorer le modèle (au fait, pardonnez ma terrible écriture).

    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; pour ce code, en fait, peu importe que nous utilisions dp[1][0] = 1 ou dp[0][1] = 1, car nous voulons faire correspondre l'index à m et n, nous étendons une ligne supplémentaire et colonne lorsque nous initialisons le tableau, voir : 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];  
    }

Il n'y a rien de particulièrement difficile à réaliser, il suffit de considérer la chose bloquée mais c'est facile à penser, ce qui implique que lorsqu'il y en a une bloquée, la grille qui est à gauche ou en bas jusqu'à celle bloquée ne peut pas être atteint par cette direction. (la grille gauche de la grille A est bloquée, nous ne pouvons pas passer de la gauche de A à A, nous ne pouvons trouver que la route montante, et cette logique fonctionne également pour le haut)

343. Rupture entière

Étant donné un entier n, divisez-le en la somme de k entiers positifs, où k >= 2, et maximisez le produit de ces entiers.

Renvoyez le maximum de produit que vous pouvez obtenir.

Exemple 1 :

Entrée : n = 2
Sortie : 1
Explication : 2 = 1 + 1, 1 × 1 = 1.
Exemple 2 :

Entrée : n = 10
Sortie : 36
Explication : 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Contraintes :

2 <= n <= 58
Page originale

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!