3-10 动态规划的课前题目
# 动态规划的课前题目
先看一道课前题目，然后跟着视频我们一起Coding。
# 什么是动态规划？
Dynamic->形容词（类似厉害、棒！）
Programming -> 规划（机器帮人规划）
动态规划(DP)是一种编程手段，动态说的是它比较厉害（Amazing!)，这是当年作者起的名字。跳过这个形容词，我们重点说说什么是规划类问题：
规划（Programming)，就是帮人寻找最优解，比如说：
- 安排课表
- 寻找最优路径（走迷宫并且吃到最多的金币）
- 找到两个单词间的最小编辑距离（将abc修改为abed的最小修改次数）
- 如何利用有限的背包装更有价值的东西……
- 找到两颗树的差异
- ……
# 题目
有一个n*n的地图，地图每个格子上有数量不等的金币。有一个游戏角色，从Start出发，到End位置。限定只可以有3种走法：
- 向下
- 向右
- 向右下
请问： 如何走是最优的，可以吃到最多的金币?
例如，如果地图是这个样子：
那么得到的路径是这样的：
写一个程序输出这条最优路径。
分析
思考如果知道某个位置相邻的所有位置的最优解， 是不是可以构造出这个位置的最优解？也就是最优解之间存在着关系。如果用bestChoice(x, y)代表位置(x, y)的最优解，位置(x,y)的金币数量为P，那么bestChoice(x, y)和下面3个位置的解存在着关系。
bestChoice(x, y) = max(
bestChoice(x-1, y-1), // 对角线
bestChoice(x, y-1),// 上方
bestChoice(x-1, y) // 左边
) + P
这是一种递归关系，可以考虑用递归函数解决，例如：
bestChoice(x, y) {
if(x == 0 && y == 0) {
return 0;
}
if(x == 0) {
return -1000;
}
if(y == 0) {
return -1000;
}
return max(
bestChoice(x-1, y-1), // 对角线
bestChoice(x, y-1),// 上方
bestChoice(x-1, y) // 左边
) + map[y-1][x-1];
}
上面的三个递归终止条件 是为了保护校验关系。这里虚构了x=0，y=0的情况，start的位置是0,0；地图左上角坐标是(1,1)。-1000 在算法设计中称为哨兵，这个设计可以让游戏角色肯定会从(0,0)出发，从而减少边界判断。
思考：上面的设计中，时间复杂度是多少？
bestChoice(10, 10) ->
bestChoice(9,9)
bestChoice(10, 9)
-> bestChoice(9, 9)
bestChoice(9, 10)
-> bestChoice(9, 9)
这样的递归计算中存在重复的情况，并不是bestChoice(9,9)重复这么简单，而是bestChoice(9,9)之下的所有递归，都被多次运算。但是有一种更简单的思考方式，上面的程序实际上是一棵3叉树，树的高度接近10。这种情况下，时间复杂度是O(3^n)。
思考：O(3^n)是一种怎样的时间复杂度——当规模上升时远远超过人类可以承受能力的时间复杂度。
如何优化？
看下图：知道3个可以推出最后1个。
知道一排， 可以计算下一排吗？
知道一排的最优解，可以结算出所有排吗？
那么：如何计算出第一排呢？
可以在左边和上边增加一行一列：
这样是不是就逐列计算，或者逐行计算， 都可以做了？
这就是动态规划。 我们成功的通过动态规划，解决了一个规划问题——获得最多金币。 其次，我们通过动态规划，将一个 O(3^n)的算法转换成了O(n^2)的算法问题。
简单讲，我们将一个人类算力不够支撑的问题，转换为了一个算力足够的问题。
思考：实战中到底用不用动态规划？
package dynamic;
import org.junit.Test;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class BestPath {
/**
* minPath(x, y) =
* max(
* minPath(x-1, y-1),
* minPath(x-1, y),
* minPath(x, y-1)
* ) + map[x, y]
* )
*/
public List<int[]> bestChoice(int[][] map){
var L = map.length;
var dp = new int[L+1][L+1][3];
// [0,1,2] -- (minValue, y, x)
for(int i = 1; i < L+1; i++) {
dp[i][0][0] = -1000; // Integer.MIN_VALUE
dp[0][i][0] = -1000;
}
for(int y = 1; y < L+1; y++) {
for(int x = 1; x < L+1; x++) {
int max = dp[y-1][x-1][0];
int py = y-1;
int px = x-1;
if(dp[y-1][x][0] > max) {
max = dp[y-1][x][0];
px = x;
}
if(dp[y][x-1][0] > max) {
max = dp[y][x-1][0];
px = x-1;
py = y;
}
dp[y][x][0] = max + map[y-1][x-1];
dp[y][x][1] = px;
dp[y][x][2] = py;
System.out.format("fill:dp=%d, px=%d, py=%d\n", dp[y][x][0], px, py);
}
}
System.out.println("---dp table---");
for(int i = 0; i < L+ 1; i++) {
for(int j = 0; j < L+1; j++) {
System.out.format("%7d ", dp[i][j][0]);
}
System.out.println();
}
int x = L, y = L;
var path = new LinkedList<int[]>();
path.addFirst(new int[]{x-1, y-1});
while(true){
int nx = dp[y][x][1];
int ny = dp[y][x][2];
x = nx;
y = ny;
if(x == 0 && y == 0) {
break;
}
path.addFirst(new int[]{x-1, y-1});
};
return path;
}
@Test
public void test(){
var map = new int[][] {
{ 5, 4, 2, 2 },
{ 8, 0, 5, 7 },
{ 4, 1, 2, 0 },
{ 1, 4, 6, 3 }
};
var path = bestChoice(map);
System.out.println(path.stream().map(x -> String.format("(%d, %d)", x[0], x[1])).collect(Collectors.toList()));
System.out.print("best path is:");
for(var p : path) {
System.out.print(map[p[1]][p[0]]);
System.out.print("->");
}
System.out.println();
}
}