第二节 动态规划初体验

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

  斐波那契数列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系统会有防止打表的机制。因此,这种方法最好不要去使用。