동적 계획법(Dynamic Programming)

1463번: 1로 만들기(4/5)
dp[n]을 숫자 n을 1로 만들 수 있는 최소의 가짓수라 하면 dp[n-1]+1, dp[n/2]+1, dp[n/3]+1 중 하나이다.

@ https://jaemin8852.tistory.com/170

2193번: 이친수(4/5)
i의 이친수는 1 + dp[i-2] + dp[i-3] + dp[i-4] + ... + dp[1]가 된다

dp[1] = 1, dp[2] = 1

dp[i] = dp[i-1] + dp[i-2]
@ n이 커지면 int로 나타낼 수 있는 수의 범위를 초과하므로 dp를 long long 타입으로 선언해야 함

@ https://ongveloper.tistory.com/100

1904번: 01타일(4/5)

dp[1] = 1, dp[2] = 2

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

 

@ https://cryptosalamander.tistory.com/82
@ https://blog.naver.com/occidere/220787441430

11726번: 2×n 타일링(4/6)
dp[1] = 1, dp[2] = 2
dp[3] = dp[2] + dp[1]
dp[4] = dp[3] + dp[2]
dp[n] = dp[n-1] + dp[n-2]

@ https://etyoungsu.tistory.com/41

11727번: 2×n 타일링 2(4/6)
dp[1] = 1, dp[2] = 3
dp[3] = dp[1] + dp[2] + dp[1]

@ https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=namjs1540&logNo=221514271297

9465번: 스티커(4/6)

dp[0][0] = dp[1][0] = 0
dp[0][n] = arr[0][n] + max(dp[1][n-1], dp[1][n-2])
dp[1][n] = arr[1][n] + max(dp[0][n-1], dp[0][n-2])
@ dp[][]는 그 배열에 오기 까지의 최대값

@ https://githubseob.tistory.com/16
@ https://ongveloper.tistory.com/265

1699번: 제곱수의 합(4/6)
dp[i] = i
dp[i] = min(dp[i], dp[i - j * j] + 1)
@ arr[i] = i //모두 1^2으로 채웠을때의 값으로 맞추기(최대의 개수)

@ https://onecoke.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-1699-%EC%A0%9C%EA%B3%B1%EC%88%98%EC%9D%98-%ED%95%A9-dp

10844번: 쉬운 계단 수(4/7)

 

@ https://yabmoons.tistory.com/22
@ https://lesslate.github.io/onlinejudge/Baekjoon-10884%EB%B2%88/

11057번: 오르막 수(4/8)
oooo7 => xxxx6(xxxx를 oooo에 넣는다) + xxx7(xxx7을 oooo에 넣는다)
dp[i][j]는 i단계에서 값이 j일때 오르막 수의 개수
dp[1][i] = 1
dp[i][j] = dp[i][j-1] + dp[i-1][j]

 

@ https://sw-ko.tistory.com/9

12865번: 평범한 배낭(4/8)

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])

 

@ https://cocoon1787.tistory.com/206