第二节 动态规划初体验

  在完成了动态规划概念的理解之后，我们来拿一道简单的题目理解一下问题的解决过程。

  斐波那契数列F(n)。当n=1、2时，F(2)=F(1)=1;其他情况F(n)=F(n-1)+F(n-2)。我们发现，这是一个递归的过程，根据前面所学知识，不难写程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<iostream>
using namespace std;
int F(int n)
{
    if(n<3)
        return 1;
    else
        return F(n-2)+F(n-1);
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d",F(1));
    for(int i=2;i<=n;i++) {
        printf(" %d",F(i));
    }
    printf("\n");
    return 0;
}

  但是，如果把这道题用在一道题目里，可能会造成超时。因为我们在每次运算中，都要把之前的所有情况都要再计算一遍，这会造成很多浪费。如果我们把每次运算的结果存放在数组里，那么在计算F(n)时，我们只需要在存放的结果中把需要的找出来，进行计算，在存进去。下面是改进的函数F：(假设n<=1000)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<iostream>
#include<cstring>
#define N 1010
using namespace std;
int A[N];
int F(int n)
{
    if(n<3) return 1;
    if(A[n]) return A[n];
        else return A[n]=F(n-1)+F(n-2);
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(A,0,sizeof(A));
    printf("%d",F(1));
    for(int i=2;i<=n;i++) {
        printf(" %d",F(i));
    }
    printf("\n");
    return 0;
}

  当状态转移方程太过于复杂的时候，我们可以使用打表的方法——把所有的可能计算一遍，存在数组里。根据输入直接给出结果，实现方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<iostream>
#define N 1010
using namespace std;
long long A[N];
void F()
{
    A[1]=1;
    A[2]=1;
    for(int i=3;i<=1000;i++) {
        A[i]=A[i-2]+A[i-1];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    F();
    printf("%d",A[1]);
    for(int i=2;i<=n;i++)
        printf(" %d",A[i]);
    printf("\n");
    return 0;
}

  这是动态规划中的枚举法，比较暴力。水题可以尝试使用这种方法去做，但是比赛的时候，oj系统会有防止打表的机制。因此，这种方法最好不要去使用。