연속해서 뽑지 못하는 수열에서 최댓값 찾기
dp[i] : i번째 까지 마실 수 있는 포도주의 최댓값
dp[i-2] : i-2번째의 포도주를 마지막으로 마셨을 때
dp[i-3]+wei[i-1] : i-3번째의 포도주를 마지막으로 마셨을 때
dp[i-4]+wei[i-1] : i-4번쨰의 포도주를 마지막으로 마셨을 때
3잔을 연속해서 마시지 못하므로 dp[i-2]를 제외한 dp[i-3]과 dp[i-4]는 wei[i-1]를 더해준다
'알고리즘 문제 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 배낭 (평범한 배낭 문제) (0) | 2022.01.22 |
|---|---|
| 다이나믹 프로그래밍 (가장 긴 증가하는 부분 수열 LIS) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 (탑다운 형식) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 문제 (마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기) (0) | 2022.01.19 |
| DP + DFS (내리막 길) (0) | 2022.01.19 |