Dynamic Programming

백준/실버1/동전1

dp[동전 번호][현재까지 가격의 합]으로 저장할 필요가 없다.
dp[현재까지 가격의 합]으로 저장해도 충분하다.
현재가로 도달할 수 있는 바로 직전 가격들의 경우의 수를 모두 더해주면 된다.

백준/실버2/lis 개수

LIS의 경우의 수도 O(N^2) LIS 길이를 구하는 알고리즘의 원리가 동일하게 적용될 수 있다.

for rearIdx
 for frontIdx < rearIdx
  if(number[rear] > number[front]) DP[rear] += DP[front]