다 해보는 타입

어떤게 최적인지 모를 때

• 1로 만들기 f(n): n을 세가지 연산(%3, %2, -1) 으로 1을 만드는 최소 횟수 큰수로 먼저 나누는게 이득인지 알 수 없다 f(n) = min(f(n%3) + 1, f(n%2) + 1, f(n-1) + 1)

• 동전교환 f(k): k을 만들기 위한 동전 n개의 최소개수

큰수로 먼저 빼는게 이득인지 알 수 없다

f(k) = f(k - coins[i]) + 1

붕어빵 판매하기 오르막 수 붕어빵 판매하기

• 제곱 수의 합 f(n): n을 만드는 1 ~ n 까지의 각 제곱수들의 합의 최소 연산 수

큰수로 먼저 빼는게 이득인지 알 수 없다

f(n) = f(n - i^2) + 1

조건에 의해 current을 선택 할거냐 말거냐

f(current, condition) ex: f(curr, previous path/opitons/count number so on…)

• minimum sum (or tsp) 이전 지나온 길을 바탕으로 현재 길을 선택할 것이냐 말것이냐

• 색상환 (인접 조건) 현재 색을 고를 거냐 말거냐, 이전 선택한 수 (조건에 맞는) 상태변화 다음 색을 고를 경우, 이전 선택한 수 상태변화

• RGB (인접 조건) R일 경우의 해는 이전 G/B의 경우에 따라 달라진다

• 기타 분할 마지막해 f(n) 과 이전 해 f(n-1) 의 관계/경우의 수 관계

확률

장마가 찾아왔다

f(days, climbed) = days동안 climbed 기어올라올때까지의 확률 0.75 * f(days + 1, climbed + 1) + 0.25 * f(days + 1, clibmed + 2)

게임

기타

암호해독

원주율 외우기 f(begin) = min ( f(begin + i) + classify(begin, i)) i= 3,4,5 배수 길이 3 난이도 + 3글자 빼고 나머지 수열에 대한 최적해 길이 4 난이도 + 4글자 빼고 나머지 수열에 대한 최적해 ..

팰린드롬? 팰린드롬2?