algorithm - 解决算法的动态规划

Question

使用动态规划方法计算函数 H 的值 H(7)定义为 H(1)=2, H(2)=3 并且对于所有整数 i>2，我们有:H(i)=H(i-2)-H(i-1)+2。

我查找、观看视频并阅读了有关动态规划的内容。但仍在为上述问题而苦苦挣扎。我了解您通过事先解决较小的问题来解决主要问题。然后你就有更多的机会解决主要问题，因为你可以引用你以前的创立。你发现的这些先前的结果被传递到一个结果中，但这是我不能用这个问题做的。

H(1)=H(1-2)-H(1-1)+2。
H(2)=H(2-2)-H(2-1)+2。
H(3)=H(3-2)-H(3-1)+2。
H(4)=H(4-2)-H(4-1)+2。
H(5)=H(5-2)-H(5-1)+2。
H(6)=H(6-2)-H(6-1)+2。

我假设这些的简单计算应该放在一个表中，然后我应该以某种方式使用这些信息来计算 H(7)。

我的想法是完全错误的还是正确的，我不知道=[此外，这是期末考试的修订版。

Answer 1

你的任务类似于斐波那契数:)首先，我将向您解释斐波那契数列。

F(1) = 1
F(2) = 1
F(N) = F(N - 1) + F(N - 2) ，对于每个 N > 2

前几个斐波那契数:
F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3
F(5) = F(4) + F(3) = 5
...

您可以在以下位置查看更多信息:http://en.wikipedia.org/wiki/Fibonacci_number

斐波那契数列由递归关系定义。斐波那契数列是递归数列。

每个递归必须有:
1) 基本案例
2)递归关系

对于斐波那契数列，基本情况是:F(1)，等于 1 和 F(2)，也等于 <强>1 。递归关系是“连接”同一问题的较小实例的关系。对于斐波那契数列，如果您想知道 F(N) ，则必须知道 F(N - 1) 和 F(N - 2), 用于所有 N > 2，仅此而已。对于斐波那契数列，递归关系是 F(N) = F(N - 1) + F(N - 2)。

代码如下:

#include <cstdio>
#include <cstdlib>

using namespace std;

int f(int n) {

    //printf("n = %d\n", n);
    if(n == 1 || n == 2) // base case
        return 1;
    return f(n - 1) + f(n - 2); // recurrence relation

}

int main() {

    int n; scanf("%d", &n);
    printf("%d\n", f(n));

    return 0;
}

如果您删除带注释的 printf，您会发现许多 Fibonacci 值被一遍又一遍地计算，这是非常低效的。尝试为 F(45) 运行这段代码，您会明白为什么它效率很低。

这就是动态规划的用武之地。如您所见，许多斐波那契值被反复计算，我们可以使用内存将它们保存在表中，如果我们需要它们，我们可以从表中返回它们。这是代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int N = 50;

long long memo[N];

long long f(int n) {
    if(memo[n] != -1) // if we already computed the value of f(N), then return that value
        return memo[n];
    return memo[n] = f(n - 1) + f(n - 2); // else compute the value, and save it into the table
}

int main() {

    memset(memo, -1, sizeof(memo));

    memo[1] = memo[2] = 1; // add answer for base case to the table

    int n; scanf("%d", &n);
    printf("%lld\n", f(n));

    return 0;
}

最后，你的问题。

作为 Fibonacci，您可以保存 h(N) 的计算值。这是一个代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int N = 25;

int check, memo[N];

int f(int x) {
    if(memo[x] != check) // if f(n) was already computed
        return memo[x]; // return computed value
    return memo[x] = f(x - 2) - f(x - 1) + 2; // else compte given value and add it to a table
}

int main() {

    memset(memo, 63, sizeof(memo)); // very big number, if the value of h(n) is different then that very big number, then we know we have computed the value for h(n)
    check = memo[0];

    memo[1] = 2; // base case
    memo[2] = 3; // base case

    int n; scanf("%d", &n);
    printf("%d\n", f(n));

    return 0;
}