Выполнение выбора действия с использованием динамического программирования

Question

Как реализовать задачу выбора задачи с использованием динамического программирования (упражнение CLRS 16.1-1). Я реализовал его с помощью Greedy Method, который работает в линейном времени (при условии, что массив уже отсортирован с временем окончания).

Я знаю, что он представляет собой оптимальную подструктуру.

Пусть $S_{ij}$ множество мероприятий, которые начинаются после деятельности $a_i$ отделки и , что закончить до активности $a_j$ начинается. Если мы обозначим размер оптимального решения для множества $S_{ij}$ by $c[i j]$, то мы имели бы повторение

$c[i j] = c[i k] + c[k j] + 1$ 

Answer 1

Мы можем решить эту проблему с помощью динамического программирования, сохраняя состояние, которое содержит подробности о текущем индексе активности и текущее время окончания действия, которое мы сделали, по каждому показателю деятельности мы можем сделать 2 решения либо выбрать какую-либо деятельность, либо нет, и, наконец, нам нужно максимально использовать как выбор, так и рекурсию. я реализовал рекурсивное решение дп в C++:

#include<bits/stdc++.h> 

using namespace std; 

int n; 
int st[1000], en[1000]; 
int dp[1000][1000]; 

int solve(int index, int currentFinishTime){ 
    if(index == n) return 0; 
    int v1 = 0, v2 = 0; 
    if(dp[index][currentFinishTime] != -1) return dp[index][currentFinishTime]; 

    //do not choose the current activity 
    v1 = solve(index+1, currentFinishTime); 

    //try to choose the current activity 
    if(st[index] >= currentFinishTime){ 
     v2 = solve(index+1, en[index]) + 1; 
    } 
    return dp[index][currentFinishTime] = max(v1, v2); 
} 

int main(){ 
    cin >> n; 
    for(int i = 0;i < n;i++) cin >> st[i] >> en[i]; 
    memset(dp, -1, sizeof dp); 

    cout << solve(0, 0) << endl; 
return 0; 
} 

http://ideone.com/m0mxx2

В этом коде dp[index][finish time] это таблица дп используется для хранения результата.