LeetCode Day동적 프로그래밍 2부

62. 고유한 경로

m×n 그리드 위에 로봇이 있습니다. 로봇은 처음에 왼쪽 상단(즉, 그리드[0][0])에 위치합니다. 로봇은 오른쪽 하단 모서리(예: 그리드[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 중국어 웹사이트의 기타 관련 기사를 참조하세요!