《1》划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（既无后效性），否则问题就无法用动态规划求解。
《2》选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
《3》确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做的，根据相邻两段的各状态之间的关系来确定决策。
《4》写出规划方程（包括边界条件）：动态规划的基本方程就是规划方程的通用形式化表达式。一般来说，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77 |
/*1、问题描述 如图，既定一个具有N层数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分， 请求出最小路径得分。 2 6 2 1 8 4 1 5 6 8*/#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>#define M 10000using
namespace std;typedef
struct Node{ int
pow,score;}Node;Node* head[M];int
main(){ int
n,i,j; Node *a,*b; printf("请输入三角形行数："); scanf("%d",&n); memset(head,NULL,sizeof(head)); for(i=1;i<=n;i++) { a=(Node*)malloc((i+1)*sizeof(Node)); for(j=1;j<=i;j++) { scanf("%d",&a[j].pow); a[j].score=a[j].pow; } head[i]=a; } <br> //初始化最底层得分 a=head[n]; for(i=1;i<=n;i++){ a[i].score=a[i].pow; }<br> //从倒数第二层开始进行动态规划 for(i=n-1;i>0;i--) { a=head[i]; b=head[i+1]; for(j=1;j<=i;j++) { a[j].score += min(b[j].score,b[j+1].score);//取左右路径中得分最小的 } } printf("最少得分：%d\n",head[1][1].score); /* for(i=1;i<=n;i++) { a=head[i]; for(j=1;j<=i;j++) { printf("%d ",a[j].pow); } printf("\n"); }*/ return
0;} |
原文：http://www.cnblogs.com/fanling999/p/3595306.html