LeetCode DayDynamic Programming Bahagian 2

62. Laluan Unik

Terdapat robot pada grid m x n. Robot pada mulanya terletak di sudut kiri atas (iaitu, grid[0][0]). Robot cuba bergerak ke sudut kanan bawah (iaitu, grid[m - 1][n - 1]). Robot hanya boleh bergerak sama ada ke bawah atau ke kanan pada bila-bila masa.

Memandangkan dua integer m dan n, kembalikan bilangan laluan unik yang mungkin boleh diambil oleh robot untuk sampai ke sudut kanan bawah.

Kes ujian dijana supaya jawapan akan kurang daripada atau sama dengan 2 * 109.

Contoh 1:

Input: m = 3, n = 7
Keluaran: 28
Contoh 2:

Input: m = 3, n = 2
Keluaran: 3
Penjelasan: Dari sudut kiri atas, terdapat sejumlah 3 cara untuk mencapai sudut kanan bawah:

1. Betul -> Bawah -> Turun
2. Bawah -> Bawah -> Betul
3. Bawah -> Kanan -> Turun

Kekangan:

1 <= m, n <= 100
Halaman Asal

Kita boleh menggunakan simulasi tatasusunan tulisan tangan ini untuk menerokai corak (secara langsung, maafkan tulisan tangan saya yang teruk).

    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; untuk kod ini, sebenarnya tidak kira sama ada kita menggunakan dp[1][0] = 1 atau dp[0][1] = 1, kerana kita ingin memadankan indeks kepada m dan n, kita melanjutkan satu baris lagi dan lajur apabila kita memulakan tatasusunan lihat: 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];  
    }

Tiada apa-apa yang sukar untuk direalisasikan, kita hanya perlu mempertimbangkan perkara yang disekat tetapi ia mudah untuk difikirkan, yang membayangkan bahawa apabila terdapat yang disekat, grid yang ditinggalkan atau ke bawah kepada yang disekat tidak boleh dicapai melalui arah ini. (grid kiri grid A ialah grid yang disekat, kita tidak boleh dari kiri A bergerak ke A, kita hanya boleh mencari laluan ke atas, dan logik ini berfungsi juga)

343. Pecah Integer

Diberi integer n, pecahkannya kepada jumlah k integer positif, dengan k >= 2, dan maksimumkan hasil darab integer tersebut.

Kembalikan produk maksimum yang anda boleh dapat.

Contoh 1:

Input: n = 2
Keluaran: 1
Penjelasan: 2 = 1 + 1, 1 × 1 = 1.
Contoh 2:

Input: n = 10
Keluaran: 36
Penjelasan: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Kekangan:

2 <= n <= 58
Halaman Asal

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

Atas ialah kandungan terperinci LeetCode DayDynamic Programming Bahagian 2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!