Как распознать проблему?

1. Ее можно разбить на маленькие под проблемы, которые пересекаются

2. У проблемы есть оптимальные подструктура, где оптимальное решение формируется из оптимальных пересекающихся подрешений оригинальной проблемы

• What is the minimum cost of doing...
• What is the maximum profit from...
• How many ways are there to do...
• What is the longest possible...
• Is it possible to reach a certain point..

3 главные компоненты, которые нужно запомнить и при построении задачи решить:

1. базовый кейс
2. recurrence relation
3. data structure - то как мы будем visit каждый семпл

Рекурсивный подсчет: Когда статичные значения для изменения state:

dp(i)=min(dp(i - 1) + cost[i - 1], dp(i - 2) + cost[i - 2])

Когда изменения не статичны и зависят от чего-то:

dp(i)=min(dp(j) + cost[j]) for all