今天来看道蓝桥杯的动态规划题：
题目描述
小蓝在一个 nn 行 mm 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第 11 行第 11 列。
小蓝可以在方格图上走动，走动时，如果当前在第 rr 行第 cc 列，他不能走到行号比 rr 小的行，也不能走到列号比 cc 小的列。同时，他一步走的直线距离不超过 33。
例如，如果当前小蓝在第 33 行第 55 列，他下一步可以走到第 33 行第 66 列、第 33 行第 77 列、第 33 行第 88 列、第 44 行第 55 列、第 44 行第 66 列、第 44 行第 77 列、第 55 行第 55 列、第 55 行第 66 列、第 66 行第 55 列之一。
小蓝最终要走到第 nn 行第 mm 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第 11 行第 11 列走到第 nn 行第 mm 列后，总的权值和最大。请问最大是多少？
输入描述
输入的第一行包含两个整数 n, mn,m，表示图的大小。
接下来 nn 行，每行 mm 个整数，表示方格图中每个点的权值。
其中，1 \leq n \leq 100，-10^4 \leq 权值 \leq 10^41≤n≤100，−10
4
≤权值≤10
4
。
输出描述
输出一个整数，表示最大权值和。
输入输出样例
示例 1
输入
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
copy
输出
15
**题解：**该题需要求最大值，初步分析应该用到动态规划，那么我们可以试着去分析下子问题的状态方程，不同于以往题的是他可以走的距离不超过三步就可以，也就是说他到达状态maxD[i,j]不只是两种走法了，变成了九种，所以应该有九个状态。maxD[i-1,j]，maxD[i-2,j]，maxD[i-3,j]，maxD[i,j-1]，maxD[i,j-2]，maxD[i,j-3]，maxD[i-1,j-1]，maxD[i-2,j-1]，maxD[i-1,j-2]，那么我们要做的就是选出权值最大的一个状态，而且还需要思考在什么条件下，它存在以下九个状态，如果横坐标小于3，那显然没有九种走法。我们可以设置二维状态数组maxD[n+1][m+1]，
那么就存在如下九个状态：
（1） if (j-1>= 1) max = Math.max(maxD[i][j-1],max);
（2） if(j-2>=1) max=Math.max(maxD[i][j-2],max)；
（3） if(j-3>=1) max=Math.max(maxD[i][j-3],max)；
（4） if(i-1>=1) max=Math.max(maxD[i-1][j],max)；
（5） if(i-1>=1 && j-1>=1) max=Math.max(maxD[i-1][j-1],max)；
（6） if(i-1>=1 && j-2>=1) max=Math.max(maxD[i-1][j-2],max)；
（7） if(i-2>=1) max=Math.max(maxD[i-2][j],max)；
（8） if(i-2>=1 && j-1>=1) max=Math.max(maxD[i-2][j-1],max)；
（9） if(i-3>=1) max=Math.max(maxD[i-3][j],max)；
代码如下:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] weight = new int[n+1][m+1];
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
weight[i][j] = sc.nextInt();
}
}
System.out.println(maxWeight(weight));
}
private static int maxWeight(int[][] weight) {
int row = weight.length;
int col = weight[0].length;
int[][] maxD = new int[row+1][col+1];
int max = -1000000;
for (int i=1;i<=row;i++){
for (int j=1;j<=col;j++){
if (i ==1&&j==1) {
maxD[i][j] = weight[i][j];
continue;
}
if (j-1>= 1) max = Math.max(maxD[i][j-1],max);
if(j-2>=1) max=Math.max(maxD[i][j-2],max);
if(j-3>=1) max=Math.max(maxD[i][j-3],max);
if(i-1>=1) max=Math.max(maxD[i-1][j],max);
if(i-1>=1 && j-1>=1) max=Math.max(maxD[i-1][j-1],max);
if(i-1>=1 && j-2>=1) max=Math.max(maxD[i-1][j-2],max);
if(i-2>=1) max=Math.max(maxD[i-2][j],max);
if(i-2>=1 && j-1>=1) max=Math.max(maxD[i-2][j-1],max);
if(i-3>=1) max=Math.max(maxD[i-3][j],max);
maxD[i][j] = max+weight[i][j];
}
}
return maxD[row][col];
}
