Добавление заметок - Динамическое программирование

Question

В настоящее время я занимаюсь динамическим программированием, и я натолкнулся на проблему Circus Tower.
Я решил проблему с динамическим программированием и реализовал ее с помощью рекурсии. Я тестировал его с небольшим количеством входов и, похоже, работал нормально.

Теперь я пытался несколько часов пытаться выяснить, как добавить меморандум в мое решение.

Вопросы

1. Как я могу добавить рабочее запоминание к моему решению. Где моя ошибка в этом случае?
2. Есть ли какое-либо эмпирическое правило или рекомендации о том, как добавлять мемуары вообще.

---

Цирк башня Проблема: цирк проектирует башню людей, стоящих на вершине друг друга плечами. Каждый человек должен быть как короче, так и легче, чем человек ниже него. Учитывая высоты и веса каждого человека в цирке, напишите способ вычисления максимально возможного числа людей в такой башне.

Мое решение & Код
Динамическое программирование

OPT[N,P] = highest tower with N given persons and person P is at the top 
---------------------------------------------------------- 
OPT[0,P]        = 0 
OPT[i,P] where person i can be above P = max(OPT[i-1,i]+1,OPT[i-1,P]) 
OPT[i,P] else       = OPT[i-1,P] 

Код:

struct Person{ 
    int ht; 
    int wt; 
}; 

// Without Memoization 
int circusTower(int n, Person* top, std::vector<Person>& persons){ 
    if (n == 0) 
     return 0; 

    if (top == NULL || top->ht > persons[n - 1].ht && top->wt > persons[n - 1].wt) 
     return max(circusTower(n - 1, &persons[n - 1], persons) + 1, circusTower(n - 1, top, persons)); 
    else 
     return circusTower(n - 1, top, persons); 
} 

// With Memoization 
int circusTower(int n, Person* top, std::vector<Person>& persons, std::vector<int>& memo){ 
    if (n == 0) 
     return 0; 

    int result; 
    if (memo[n-1] == 0) { 
     if (top == NULL || top->ht > persons[n - 1].ht && top->wt > persons[n - 1].wt) 
      result = max(circusTower(n - 1, &persons[n - 1], persons, memo) + 1, 
         circusTower(n - 1, top, persons, memo)); 
     else 
      result = circusTower(n - 1, top, persons, memo); 

     memo[n - 1] = result; 
     return result; 
    } else { 
     return memo[n-1]; 
    } 
} 

Главная - тест:

int main(){ 
    std::vector<Person> persons = { {65, 100},{100, 150},{56, 90}, {75, 190}, {60, 95},{68, 110} }; 
    std::stable_sort(persons.begin(), persons.end(), sortByWt); 
    std::stable_sort(persons.begin(), persons.end(), sortByHt); 

    std::vector<int> memo(6,0); 

    //Without memoization 
    cout << circusTower(6, NULL, persons) << endl; 
    //With memoization 
    cout << circusTower(6, NULL, persons, memo) << endl; 
} 

В примере внутри й е основные выше, правильный результат 5. Моего регулярное решения (без запоминания) печатает 5, но с запоминанием печатает 6.

Answer 1

Вашего метод зависит от 3-х аргументов но memoize только из первого аргумента n

Действительно, в вашем случае третий (persons) является постоянным, , но второй (top) изменяется во время рекурсивного вызова.

так из-за ваше запоминание, как после возвращения такого же значения:

• circusTower(n - 1, &persons[n - 1], persons, memo)
• circusTower(n - 1, top, persons, memo)