动态规划求解算法

Question

用动态规划方法计算定义的函数H的值H(7)，使得H(1)=2，H(2)=3，对于所有整数i>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

您的任务类似于fibonnaci :)首先，我将解释fibonacci。

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

..。

您可以在以下网站上看到更多信息：number

Fibonacci数的Fibonacci序列是由递推关系定义的。Fibonacci序列是递归序列。

每个递归都必须有：

( 1)基本案件

2)递推关系

在Fibonacci的情况下，基本情况是：F(1)，它等于1，F(2)也等于1。递归关系是将同一问题的较小实例“连接”起来的关系。对于斐波那契数，如果你想知道F(N)，你必须知道F(N-1)和F(N-2)，对于所有N > 2，就是这样。在Fibonacci情况下，递推关系为 F(N ) =F(N1)+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;
}

Answer 2

你被给予了

H(1)=2
H(2)=3

根据这些信息和H(i)的公式，您可以按以下方式计算H(3)

H(3) = H(3-2) - H(3-1) + 2 = H(1) - H(2) + 2 = 2 - 3 + 2 = 1

冲洗并重复。

Answer 3

H(1) =2

H(2) =3

H(3) = H(1) - H(2) +2=2-3+2=1

H(4) = H(2)- H(3) +2=3-1+2=4

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

H(6) = H(4) - H(5) +2=4- (-1) +2=7

H(7) = H(5) - H(6) +2=-1-7+2= -6

所以H(7)是-6