배낭 문제

• 이 문제가 왜 DP 문제인가?

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + item[i].weight)

dp[ i ][ j ] → i번째 아이템까지 결정했을 때 무게가 j 일 때의 최대 가치

→ 이는 i 번째 아이템을 넣었거나, i 번째 아이템을 넣지 않았을 때의 가치 중 더 큰 것

• base condition

  i == 0 이거나 j == 0 일때의 가치는 0

• 예제

  • 배낭에 최대 6을 담을 수 있다고 할 때 최대 가치는?
    • 아이템 [ weight, value ]
    • [ (3,4), (1,2), (6,5), (5,6), (1,2), (3,3) ]
  • 배낭에 최대 5를 담을 수 있다고 할 때 최대 가치는?
    • [ (1,15), (3,20), (4,30) ]

• 사실 재귀랑 다를게 없지만, dp 테이블을 작성해 중복된 계산을 막는다는 의미가 있음

LCS

dp[i][j] → A의 i번째 문자열과 B의 j번째 문자열까지의 가장 긴 공통 문자열 길이

dp[i][j] = dp[i - 1][j - 1] + 1 if A[i] == B[i]
				 = max(dp[i - 1][j], dp[i][j - 1]) if A[i] != B[i]

• 왜 DP인가?
  • 이전 테이블의 값을 가지고 새로운 LCS를 구할 수 있기 떄문에