概述
动态规划处理的对象是多阶段策略问题。
多阶段策略问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数衡量该策略的优劣。多阶段策略问题的最优化目标是获取导致问题最优值的最优决策序列即得到最优解。
应用动态规划设计使多阶段决策过程达到最优(成本最省、效益最高、路径最短)，依据动态规划的最优性原理: 作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。也就是说，最优决策序列中的任何子序列都是最优的。
动态规划实施步骤
把所求最优化问题分成若干阶段，找出最优解的性质，并刻画其结构特性
最优子结构特性是动态规划求解问题的必要条件，只有满足最优子结构特性的多阶段决策问题才能应用动态规划设计步骤。
将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推(或递归)关系，并确定初始条件。
通过设置相应的函数表示各个阶段的最优值，分析归纳出各个阶段状态之间的转移关系，是应用动态规划设计求解的关键。
应用递推(或递归)求解最优值
递推(或递归)计算最优值是动态规划算法的实施过程。具体应用与所设置的表示各个阶段最优值的函数密切相关。
根据计算最优值时所得到的信息，构造最优解
构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题的具体实际记录必要的信息，根据所记录的信息构造出问题的最优解。
以上步骤前3个是动态规划设计求解最优化问题的基本步骤。当只需求解最优值时，第4个步骤可以省略。若需求出问题的最优解，则必须执行第4个步骤。
相关例题
1.最优路径搜索
点数值三角形是一个二维数组：三角形由n行构成，第k行有k个点，每一个点都带有一个数值。寻找从顶点开始每一步可沿左斜或右斜向下至底的一条路径，使该路径所经过的点的数值和最小。
比如输入n为3，三角形为：
口
口 口
口 口 口
分析
建立数组dp[i] [j] 表示点(i,j)到底的最小数值和，从下往上推，状态转移方程为:
dp[i] [j]=ar[i] [j]+min{dp[i+1] [j],dp[i+1] [j+1]}
dp[0] [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
| import java.util.Scanner;
public class 最优路劲搜索_动态规划 {
static int dp[][];
static int ar[][];
static int n;
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
n=in.nextInt();
dp=new int [30][30];
ar=new int [30][30];
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
ar[i][j]=in.nextInt();
dp();
System.out.println(dp[0][0]);
}
public static void dp(){
for(int i=n-1;i>=0;i--)
for(int j=0;j<=i;j++)
dp[i][j]=ar[i][j]+Math.min(dp[i+1][j], dp[i+1][j+1]);
}
}
|
2.矩阵权值最长路径
一个矩阵从(1,1)出发 到(m,n)找出权值最大的路径，只能往下或往右走。
分析
建立dp[i] [j]表示从(1,1)走到点(i,j)的权值最大的路径，因为只能往下或往右走，状态转移方程为:
dp[i] [j]=list[i] [j]+max{dp[i-1] [j],dp[i] [j-1]}
dp[m] [n]即为问题解
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
| import java.util.Scanner;
public class 矩阵权值最长路径 {
static int n,m;
static int dp[][],list[][];
public static void main(String[] args){
Scanner in=new Scanner(System.in);
n=in.nextInt();
m=in.nextInt();
list=new int [n+1][m+1];
dp=new int [n+1][m+1];
for(int q=1;q<=n;q++)
for(int w=1;w<=m;w++)
list[q][w]=in.nextInt();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=max(dp[i][j-1],dp[i-1][j])+list[i][j];
System.out.println(dp[n][m]);
}
static int max(int x,int y){
if(x>y) return x;
else return y;
}
}
|
3.传球游戏
【问题描述】
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。
输入格式
共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。
输出格式
t共一行，有一个整数，表示符合题意的方法数。
样例输入
3 3
样例输出
2
分析
建立dp[i] [j] 表示传i次传到j手中，初始条件dp[0] [1]=1;(传0次传到1手中),状态转移方程:
- j==1(传到1手中), dp[i] [j]= dp[i-1] [n] (传i-1次传到n，因为队列是循环的，n之后又回到1)+dp[i-1] [2] (传i-1次传到2，2也可以传到1)
- j==n(传到n手中,n可以从n-1和1传到) ，dp[i] [j]=dp[i-1] [n-1]+dp[i-1] [1]
- 其他, dp[i] [j]=dp[i-1] [j-1]+dp[i-1] [j+1]
dp[m] [1] (传m次传到1)即为答案
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| import java.util.Scanner;
public class 传气球_动态规划 {
static int m,n;
static int dp[][];
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
n=in.nextInt();
m=in.nextInt();
dp=new int [40][40];
dp[0][1]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
if(j==1) dp[i][j]=dp[i-1][n]+dp[i-1][2];
else if(j==n) dp[i][j]=dp[i-1][n-1]+dp[i-1][1];
else dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
System.out.println(dp[m][1]);
}
}
|
4.结点选择(树形动态规划)
问题描述
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
输入格式
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
输出格式
输出一个整数，代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
样例说明
选择3、4、5号点，权值和为 3+4+5 = 12 。
数据规模与约定
对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。
分析
这是一道树形动态规划题目，需要用dfs遍历树，再通过动态规划求解。
建立dp[] [],dp[i] [0]表示i结点不选时的最大权值，dp[i] [1]表示i结点选择时的最大权值
状态转移方程：
- dp[i] [1]=dp[i] [1]+dp[j] [0] (j为i的子节点,因为i已经选了，所以j不能选)
- dp[i] [0]=dp[i] [0]+max{dp[j] [0],dp[j] [1]}(i结点不选, 则比较j结点选和不选哪个权值比较大)
最后题目解为max{dp[1] [0],dp[1] [1]} (选择1结点或不选择1结点)
代码
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
| import java.util.Scanner;
public class 结点选择_动态规划_树形结构 {
static int n;
static int dp[][],list[][];
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
n=in.nextInt();
dp=new int [100001][2];
list=new int [100001][300];
for(int i=1;i<=n;i++){
dp[i][1]=in.nextInt();
}
for(int j=1;j<n;j++){
Add(in.nextInt(),in.nextInt());
}
dp(1,0);
System.out.println(max(dp[1][0],dp[1][1]));
}
static void Add(int a,int b){
int i=0,j=0;
while(true){
if(list[a][i]!=0) i++;
else{
list[a][i]=b;break;
}
}
while(true){
if(list[b][j]!=0) j++;
else{
list[b][j]=a;break;
}
}
}
static void dp(int son,int father){
int son1;
for(int i=0;list[son][i]!=0;i++){
son1=list[son][i];
if(son1!=father){
dp(son1,son);
dp[son][1]+=dp[son1][0];
dp[son][0]+=max(dp[son1][0],dp[son1][1]);
}
}
return ;
}
static int max(int x,int y){
if(x>y) return x;
else return y;
}
}
|
5.K好数
问题描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。
输入格式
输入包含两个正整数，K和L。
输出格式
输出一个整数，表示答案对1000000007取模后的值。
样例输入
4 2
样例输出
7
数据规模与约定
对于30%的数据，KL <= 106；
对于50%的数据，K <= 16， L <= 10；
对于100%的数据，1 <= K,L <= 100。
分析
K进制的大概意思是它每一位的组成只能从0-k-1中选取，如果想直接求L位长的K进制数有多少K好数，可能有些复杂。先从L=1开始求,再从L=2,L=3 以此类推，便可以通过累加得出L位长的K好数总共有多少了。
建立dp[i] [j]表示i长度，j为开头数字满足K好数的个数
比如K=3，L=1，此时的K好数分别为0、1、2.即dp[1] [0]=1,dp[1] [1]=1,dp[1] [2]=1
L=2时,此时的K好数分别为oo、02,11，20、22
所以状态方程为:
1
2
3
4
5
| for(int n=0;n<K;n++){
if(n!=j+1&&n!=j-1){
dp[L][j]+=dp[L-1][n];
}
}
|
代码
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
| import java.util.Scanner;
public class K好数_动态规划 {
static int K,L;
static long dp[][];
static long mod=1000000007,sum;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
K=in.nextInt();
L=in.nextInt();
dp=new long [L][K];
for(int q=0;q<K;q++) dp[0][q]=1;
for(int i=1;i<L;i++)
for(int j=0;j<K;j++)
for(int x=0;x<K;x++){
if(x!=j-1&&x!=j+1){
dp[i][j]+=dp[i-1][x];
dp[i][j]%=mod;
}
}
for(int y=1;y<K;y++){
sum+=dp[L-1][y];
sum%=mod;
}
System.out.println(sum);
}
}
|
6.被3整除的子序列
题目描述
给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模
输入描述:
输出描述:
示例1
输入
输出
分析
一个数的位数相加如果能被3整除的话，这个数就能被三整除，长度最大为50所以和数最大为50*9=450。dp[i] [j]表示前i位能组成和数为j的个数。状态转移方程：
1
2
3
4
5
6
7
| for(int i=1;i<=len;i++)
for(int j=0;j<500;j++){
dp[i][j]=dp[i-1][j];
if(j==f(ar[i-1])) dp[i][j]++;
if(j>=f(ar[i-1])) dp[i][j]+=dp[i-1][j-f(ar[i-1])];
dp[i][j]%=mod;
}
|
代码
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
| import java.util.Scanner;
public class 被三整除的整数列_动态规划 {
static char ar[]=new char [55],a[];
static long dp[][]=new long[55][555];
static int len=0;
static long mod=(long)(1e9+7),count=0;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
a=in.next().toCharArray();
len=a.length;
for(int x=0;x<len;x++)
ar[x]=a[x];
dp();
}
static int f(char c){
return c-'0';
}
public static void dp(){
for(int i=1;i<=len;i++)
for(int j=0;j<500;j++){
dp[i][j]=dp[i-1][j];
if(j==f(ar[i-1])) dp[i][j]++;
if(j>=f(ar[i-1])) dp[i][j]+=dp[i-1][j-f(ar[i-1])];
dp[i][j]%=mod;
}
for(int k=0;k<500;k++){
if(k%3==0)
count=(count+dp[len][k])%mod;
}
System.out.println(count);
}
}
|
