LeetCode Day동적 프로그래밍 5부

518. 코인 체인지 II

다양한 액면가의 동전을 나타내는 정수 배열 동전과 총 금액을 나타내는 정수 금액이 제공됩니다.

해당 금액을 구성하는 조합의 수를 반환합니다. 해당 금액을 코인 조합으로 채울 수 없는 경우 0을 반환합니다.

각 코인의 수는 무한하다고 가정할 수 있습니다.

답은 부호 있는 32비트 정수에 맞도록 보장됩니다.

예 1:

입력: 수량 = 5, 코인 = [1,2,5]
출력: 4
설명: 금액을 보충하는 방법에는 네 가지가 있습니다:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
예시 2:

입력: 수량 = 3, 코인 = [2]
출력: 0
설명: 2개의 동전만으로는 3개의 금액을 만들 수 없습니다.
예시 3:

입력: 금액 = 10, 코인 = [10]
출력: 1

제약사항:

1 <= 동전.길이 <= 300
1 코인의 모든 가치는 고유합니다.
0 원본페이지

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length+1][amount+1];
        for(int i=0; i<=coins.length; i++){
            dp[i][0] = 1;
        }
        for(int i=1; i<= coins.length; i++){
            for(int j=1; j<=amount; j++){
                if(j<coins[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }

            }
        }
                    // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[coins.length][amount];
    }

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i=0; i< coins.length; i++){
            for(int j=coins[i]; j<=amount; j++){
                dp[j] = dp[j] + dp[j-coins[i]];
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[amount];
    }

377. 조합 합 IV

고유한 정수 배열 nums와 대상 정수 target이 주어지면 대상에 합산되는 가능한 조합의 수를 반환합니다.

답안이 32비트 정수에 맞도록 테스트 사례가 생성되었습니다.

예 1:

입력: 숫자 = [1,2,3], 대상 = 4
출력: 7
설명:
가능한 조합 방법은 다음과 같습니다:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
서로 다른 시퀀스는 서로 다른 조합으로 계산됩니다.
예시 2:

입력: 숫자 = [9], 대상 = 3
출력: 0

제약사항:

1 <= nums.length <= 200
1 숫자의 모든 요소는 고유합니다.
1

추가 작업: 주어진 배열에 음수가 허용되면 어떻게 되나요? 문제가 어떻게 바뀌나요? 음수를 허용하려면 질문에 어떤 제한을 추가해야 합니까?

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i=1; i<=target; i++){
            for(int j=0; j<nums.length; j++){
                if(nums[j] <= i){
                    dp[i] = dp[i] + dp[i-nums[j]];
                }
            }
            // System.out.println(Arrays.toString(dp));
        }
        return dp[target];
    }

위 내용은 LeetCode Day동적 프로그래밍 5부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!