Понимание динамического программирования с помощью рекурсии

Несколько лет назад мне было трудно понять, как работает концепция динамического программирования (DP). Здесь я хотел бы поделиться тем, как я изучил DP, начав с рекурсии.

Рекурсия

Первый шаг: разбейте проблему на подзадачи.
Второй шаг: остановите подзадачи (базовый случай).

Пример: Допустим, как мы вычисляем 1+2+3+..+n (рекурсия)?

Пусть sum(n) = (1+2+…+n)
Первый шаг: sum(n)= sum(n-1) + n
Второй шаг: sum(1) = 1

// Recursion
int sum(int n){
   if(n==1) return 1;  // second step
   return sum(n-1) + n; // first step
}

Динамическое программирование (DP)

Как насчет написать в форме DP?

Первый шаг: Начните с подзадач (базовый вариант).
Второй шаг: Объедините подзадачи, чтобы решить большую проблему.

Разберем тот же вопрос…
Первый шаг: sum[1] = 1
Второй шаг: sum[n] = sum[n-1]+n;

// DP
int sum[] = new int[n+1];
sum[1] = 1;                 // first step
for(int i=2;i<=n;i++)       
   sum[n] = sum[n-1] + n;   // second step

Давайте попробуем другой пример: последовательности Фибоначчи.
0, 1, 1 ,2 ,3 ,5 ,8 ,…
Как мы можем найти n член числа Фибоначчи?

Пусть fib(n) — это n-й член числа Фибоначчи.
Давайте программировать!

// Recursion
int fib(int n){
   if(n==0||n==1) return n;    // second step
   return fib(n-1) + fib(n-2); // first step
}

Как насчет ДП?

// DP
int fib[] = new int[n];
fib[0] = 0;                      // first step
fib[1] = 1; 
for(int i=2;i<=n;i++)
   fib[i] = fib[i-1] + fib[i-2]; // second step;

Различия между рекурсией и DP?

DP использует массив для хранения ответа на подзадачу, а рекурсия — нет.
DP быстрее вычисляет результат при вычислении числа Фибоначчи.

Давайте попробуем задать более сложный вопрос!

Вопрос: (Проблема с раздачей монет)
Если у вас неограниченное количество жетонов монет = {1,3,5}. Выясните, сколькими способами (без учета порядка) можно составить его, если общая стоимость монет (монет) равна n.

Для n = 4, 4 = 1+1+1+1, 4 = 1+3
путь(4) = 2
Примечание: путь(0) = 1, потому что если вы не использовали любой жетон монеты, тогда сумма монет равна 0. Есть и один способ!

// Recursion
int way(int n,int index,int token[]){
   if(n==0) return 1;                       // second step
   int total = 0;
   for(int i=index;i<token.length;i++)
      if(n-token[i]>=0)
         total += way(n-token[i],i,token);  // first step
   return total;
}
// int token[] = {1,3,5};
// way(4,0,token) = 2
// way(5000,0,token) = 834834 // very slow

Это может быть слишком медленно, когда значение n становится больше. Попробуем ДП!

// DP
int token[] = {1,3,5};
int way[] = new int[n+1];
way[0] = 1;                      // first step
for(int i=0;i<token.length;i++)
   for(int j=token[i];j<=n;j++)
      way[j] += way[j-token[i]]; // second step
// way[4] = 2
// way[5000] = 834834

Вот как я понимаю DP, надеюсь, это сработает и для вас.

Понимание динамического программирования с помощью рекурсии

Похожие вопросы