DP(동전 교환, LCS)

동전 교환

동전 교환 관련 문제 접근 :: 마이구미

 

n가지 종류의 동전을 갖고 가치의 합이 k원이 되는 경우의 수.

dp[0] = 1; 
for (int i = 0; i < n; i++) { 
	for (int j = coin[i]; j <= k; j++) { 
    	dp[j] = dp[j] + dp[j - coin[i]]; 
        } 
 }

 

n가지 종류의 동전을 갖고 가치의 합이 k원이 되도록한다. 이때 동전의 개수는 최소가 되려고 한다.

Arrays.fill(dp, 10001); 
dp[0] = 0; 
for (int i = 0; i < n; i++) { 
	for (int j = coin[i]; j <= k; j++) { 
		dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1); 
	} 
}

 

LCS

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence