c++ - 添加内存 - 动态规划

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;
}

在上面 main 的例子中，正确的结果是 5。我的常规解决方案(没有内存)打印 5，但是有内存它打印 6。

Answer 1

您的方法依赖于 3 个参数但你只从第一个参数 n

内存

确实在你的情况下，第三个(persons)是不变的，但第二个 (top) 在递归调用期间发生变化。

所以由于你的内存，以下两个错误地返回相同的值:

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