动态规划的课前题目

先看一道课前题目，然后跟着视频我们一起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();

    }
}

动态规划的课前题目 ​

什么是动态规划？ ​

题目 ​

动态规划的课前题目

什么是动态规划？

题目