LeetCode .잔돈 교환(동적 기획)

9017 단어 LeetCode동적 기획
1、
액면가가 다른 동전 코인과 총 금액 아몬드를 정한다.총 금액을 모으는 데 필요한 최소한의 동전 개수를 계산하기 위해 함수를 작성해라.만약 어떤 동전 조합도 총 금액을 구성할 수 없다면, -1로 되돌아간다.
예1:·입력:coins=[1,2,5],amount=11·출력:3·해석:11=5+5+1
#include 
#include 
using namespace std;
class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		//dp[i]：i          
		vector<int>dp(amount + 1, INT_MAX);
		dp[0] = 0;
		//      ，        ，          ，         
		for (int i = 1; i <= amount; ++i)
			for (int j = 0; j < coins.size(); j++)
				if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX)
					//  i         <<>>   (i-coins[j])         +1【   coins[j]  】
					dp[i] = min(dp[i], dp[i - coins[j]] + 1);
		return dp[amount] == INT_MAX ? -1 : dp[amount];
	}
};

2、
액면가가 다른 동전과 총 금액을 정하다.함수를 써서 총 금액을 모을 수 있는 동전의 조합수를 계산하다.모든 액면가의 동전이 무한하다고 가정해 보세요.
예1: 입력:amount=5,coins=[1,2,5] 출력: 4 해석: 4가지 방법으로 총 금액을 모을 수 있다. 5=5(잔돈 5+dp[0]로 사용) 5=2+2+1(잔돈 2+dp[3]로 사용) 5=2+1+1+1+1(잔돈 2+dp[3]로 사용) 5=1+1+1+1+1(잔돈 1+dp[4]로 사용)
#include 
using namespace std;
class Solution {
public:
	int change(int amount, vector<int>& coins) {
		//dp[i]：    i        (   )
		vector<int> dp(amount + 1, 0);
		//   coins     coins     1
		dp[0] = 1;

		//       ，     ，         ，  5=(2)+2+1=(1)+2+2
		//        ，      ，                    
		// ==>>	          ，        coins[0..j-1]   ，
		//		   coins[j]   ，        ，      。

		//        
		for (int j = 0; j < coins.size(); j++)
			//    coins[j]    ，                 

			for (int i = coins[j]; i < amount + 1; i++)
				dp[i] += dp[i - coins[j]];
		return dp[amount];
	}
};
링크 ux 커 널 기초 층 의 학습 (1)
해커 등급: 세 쌍둥이 비교

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage