~~재제출 죄송합니다.~~

1로 만들기

문제 링크

http://icpc.me/1463

풀이

dp[i] = i를 1로 만들기 위해 필요한 최소 연산 횟수
dp[i] = min({dp[i-1], dp[i/2], dp[i/3]}) + 1

2n 타일링

문제 링크

http://icpc.me/11726

풀이

dp[i] = 2*i를 만드는 경우의 수
dp[i] = dp[i-1] + dp[i-2]

연속합

문제 링크

http://icpc.me/1912

풀이

그리디로 푸는 것이 더 편합니다.

#include <stdio.h>

int main(){
	int n;
	int max = -2147483648;
	int now = 0;
	int arr[100010] = {0};
	scanf("%d", &n);
	for(int i=0; i<n; scanf("%d", &arr[i++]));
	for(int i=0; i<n; i++){
		now = (now>0?now:0)+arr[i];
		max = max>now?max:now;
	}
	printf("%d", max);
}

계단 오르기

문제 링크

http://icpc.me/2579

풀이

dp[i] = i번째까지의 최댓값, stair[i] = i번째의 점수
case 1) n-1번째 계단을 밟는다. => n-2번째 계단을 못 밟음
case 2) n-1번째 계단을 밟지 않는다. => n-2번째 계단을 무조건 밟음

dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i])

2n 타일링2

문제 링크

http://icpc.me/11727

풀이

dp[i] = dp[i-1] + 2*dp[i-2]

타일 채우기

문제 링크

http://icpc.me/2133

풀이

Bit DP

제곱수의 합

문제 링크

http://icpc.me/1699

풀이

dp[i] = i를 제곱수들의 합으로 표현할 때, 항의 최소 개수
dp[i] = min(dp[i-jj]+1) (when 1 ≤ jj ≤ i)

카드 구매하기

문제 링크

http://icpc.me/11052

풀이

dp[i] = max(dp[i-j] + p[j]) (when 1 ≤ j ≤ i)

이친수

문제 링크

http://icpc.me/2193

풀이

dp[i][j] = 길이가 i면서 j로 끝나는 경우의 수
dp[i][0] = dp[i-1][0] + dp[i-1][1]
dp[i][1] = dp[i-1][0]

쉬운 계단 수

문제 링크

http://icpc.me/10844

풀이

dp[i][j] = 길이가 i면서 j로 끝나는 경우의 수

스티커

문제 링크

http://icpc.me/9465

풀이

위에 있는 스티커를 사거나(1), 밑에 있는 스티커를 사거나(2), 안 사거나(0)

dp[i][0] = max({dp[i-1][1], dp[i-1][2], dp[i-1][0]});
dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + arr[i][1];
dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + arr[i][2];

포도주 시식

문제 링크

http://icpc.me/2156

풀이

dp[i] = max({dp[i-3]+arr[i-1]+arr[i], dp[i-1], dp[i-2]+arr[i]});

가장 긴 증가하는 부분 수열

문제 링크

http://icpc.me/11053

풀이

dp[i] = i번째 수로 끝나는 가장 긴 증가하는 부분 수열

dp[i] = max(dp[j]+1) (when j < i and a[j] < a[i])
ans = max(dp[i]) (when i <= n)

오르막 수

문제 링크

http://icpc.me/11057

풀이

dp[i][j] = 길이가 i면서 j로 끝나는 경우의 수

합 분해

문제 링크

http://icpc.me/2225

풀이

dp[i][j] = j개의 숫자를 더해서 i를 만드는 경우의 수

#include <bits/stdc++.h>
using namespace std;

const int m = 1e9;

int dp[444][444];

int main(){
	int a, b; cin >> a >> b;
	for(int i=0; i<=a; i++){
		for(int j=1; j<=b; j++){
			if(j == 1){
				dp[i][1] = 1;
				continue;
			}
			for(int k=0; k<=i; k++){
				dp[i][j] += dp[i-k][j-1]%m; dp[i][j] %= m;
			}
		}
	}
	cout << dp[a][b];
}