leetcode322 잔돈 교환
1592 단어 leetecode
-1。예1: 입력:coins=[1, 2, 5],amount=11출력:3해석:11 = 5 + 5 + 1예2: 입력:coins=
[2], amount=3 출력:-1우리는 1차원 동적 그룹 dp를 유지합니다. 그 중에서 dp[i]는 돈이 i일 때의 최소 동전 수를 나타내는 거스름돈을 표시합니다. 그룹은 0에서 시작되기 때문에 우리는 한 명을 더 신청해야 합니다. 그룹의 크기는 amount+1입니다. 그러면 최종 결과는 dp[amount]에 저장될 수 있습니다.dp[0]=0을 초기화합니다. 목표치가 0이면 동전이 필요하지 않기 때문입니다.다른 값은 정형 최대치나 amount+1으로 초기화할 수 있다. 왜냐하면 가장 작은 동전은 1이기 때문에 amount는 가장 많은 amount개의 동전을 필요로 하고 amount+1도 정형 최대치의 작용에 해당한다.자, 이제 상태 이동 방정식을 찾아야 돼요. 생각이 없어요?괜찮다회귀예1, 만약에 내가 값이 5인 동전을 얻었다고 가정하면 목표치가 11이기 때문에 만약에 우리가 dp[6]를 알았다면 11을 구성하는 dp값을 알았을까?그래서 우리가 dp[i]를 업데이트하는 방법은 모든 동전을 훑어보는 것이다. 만약에 훑어보는 동전의 값이 i값보다 적다(예를 들어 우리가 5값의 동전으로 dp[3]를 업데이트할 수 없다)면 우리는 dp[i-coins[j]+1로 dp[i]를 업데이트한다. 그래서 상태 이동 방정식은 다음과 같다.
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
그 중에서coins[j]는 제j개의 동전이고, i-coins[j]는 돈 수 i를 위해 그 중의 한 동전의 값을 빼고, 나머지 돈 수는 dp수조에서 값을 찾은 다음에 1과 현재 dp수조의 값을 비교하여 비교적 작은 업데이트 dp수조를 취한다.
public int coinChange(int[] coins, int amount) {
if(coins == null || coins.length == 0 || amount <= 0) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for(int i = 1; i <= amount; i++){
for(int j = 0; j < coins.length; j++){
if(coins[j] <= i){
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return (dp[amount] > amount) ? -1 : dp[amount];
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2. Add Two Numbers(Java)제목: 두 개의 음수 가 아 닌 두 개의 링크 된 목록 이 제 공 됩 니 다. 숫자 는 역순 으로 저장 되 며 각 노드 에는 한 개의 숫자 가 포 함 됩 니 다. 두 개의 숫자 를 추가 하고 링크 된 목록 으로 반환...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
