从暴力破解到记忆搜索，再到动态规划，一个问题如何一步一步变成动态规划的

朴灿烈づ我的快乐病毒、 2023-02-18 08:26 1阅读 0赞

在这里就不得不吐槽一下学校的算法课，一上来就给我们讲动态规划什么最优子结构、套用一些公式，乱七八糟的也记不住。而实际上动态规划的发展是有一定历史的。为啥会有动态规划呢？

起初算法大牛、先贤们在研究一类问题的时候，发现计算的过程中总是出现重复计算的数据，这一部分被反复计算了好多次，后来大神们就用map这样的额外容器记录之前出现的数据，得到了一部分的优化。再后来发现了这类问题的一个规律，最后得总结出了一个动态规划。

实际上动态规划就是暴力破解的优化。学校的老师，讲算法直接就给了几个例题，然后讲，很无奈。

我们来看这样一个经典问题：

给定一个数组，这个数组是金钱的分值，\[10,5,1,25\]，里面的数值可以自己定义。然后有一个目标的钱数，aim = 2000，这个值表示数组中可以招多少个这个零钱，比如：可以200个10，400个5等等这样的，求一共有多少个方法！

### 一、暴力递归 ###

思路：当我第一个10是0个的时候，那么后面数组\[5,1,25\]就去找能够组曾1990的有多少个。

当我第一个10是1个的时候，那么后面数组\[5,1,25\]就去找能够组曾1980的有多少个。

当我第一个10是100个的时候，那么后面数组\[5,1,25\]就去找能够组曾1000的有多少个。

如果能到最后aim是0，说明该方法可行，如果大于0那么表示这个方法找不开零钱。

代码如下：

public static int coins1(int[] arr, int aim) {
            if (arr == null || arr.length == 0 || aim < 0) {
                return 0;
            }
            return process1(arr, 0, aim);
        }
    
        public static int process1(int[] arr, int index, int aim) {
            int res = 0;
            if (index == arr.length) {
                res = aim == 0 ? 1 : 0;
            } else {
                for (int i = 0; arr[index] * i <= aim; i++) {
                    res += process1(arr, index + 1, aim - arr[index] * i);
                }
            }
            return res;
        }

这个for循环代表的就是取值0 1 ... 能够取多少个。比如上面数组，第一个值最多可以有200循环，之后的问题交给剩下的元素递归。最后递归到最底部，index下标到数组长度停止，判断当前的aim是不是0，如果是0，表示本次遍历可以成功。res会把结果累计相加。

如何有的重复计算呢？

当第一个钞票10，的数量为10，第二个钞票5，数量为20的时候，后面需要aim计算aim = 1800。

当第一个钞票10，的数量为15，第二个钞票5，数量为10的时候，后面需要aim计算aim = 1800。

所以这就重复计算了，本上第一次计算过了，第二次又重复计算了一次！这种问题叫**无效性问题，就是之前的结果不会影响后面的不同，aim=1800的计算跟前面没有关系。**

### 二、记忆搜素优化 ###

我们用一个map去存储之前计算过的结果。key是当前的数组下标和aim的值，是index\_aim，例如：10\_1900。value是当前res值，表示目前有多少种方法。

/**
         * 记忆搜索方法
         */
        public static int process_map(int[] arr, int index, int aim) {
            int res = 0;
            if (index == arr.length) {
                res = aim == 0 ? 1 : 0;
            } else {
                for (int i = 0; arr[index] * i <= aim; i++) {
                    int nextAim = aim - arr[index] * i;
                    String key = String.valueOf(index + 1) + "_" + String.valueOf(nextAim);
                    if (map.containsKey(key)) {
                        res += map.get(key);
                    } else {
                        res += process_map(arr, index + 1, nextAim);
                    }
                }
            }
            map.put(String.valueOf(index)+"_"+String.valueOf(aim),res);
            return res;
        }
    
        public static int getMap(int[] arr,int aim){
            return process_map(arr,0,aim);
        }

每次相加，都去之前查询，看看是否计算过。如果计算过直接拿，否则插入。

先贤们就是这样又搞出了动态规划。

### 三、动态规划 ###

首先我们得建立dp，有什么要求吗？建立dp，看的是暴力递归得可变参数，上面可变参数是index和aim，所以是一个二维数组，

dp\[0 …… arr.length\]\[0 …… aim\]。先建立二维数组，我们以arr = \[5,3,2\] ，aim = 10为例子。这里面的值就是方法数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

我们最终取得结果在哪个位置呢？

然后我们来看一些初始化得设置，看base-case，表示只有index = arr.length得时候同时aim等于0，才是1。其他aim不等于0的情况都是0。由于递归最终都返回最上面得调用，所以是aim = 10，index = 0得时候，就是右上角

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

所以变成了这样：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]

之后我们看到

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3][]

表明形成一个记录，需要一个循环，这个循环就是下一个边界index+1，的aim -arr\[index\]\*i值，并且不出边界，随着i增加aim -arr\[index\]\*i越来越小，比如dp\[1\]\[6\]。那么就等于哪些值相加呢？arr\[1\] = 3如图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4][]

由这三个点相加。所以我们可以从数组下面依次遍历。我们先来计算index = 2那一层

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5][]

此时下一层呢？index = 1呢？arr\[1\] = 3。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6][]

**所以所，动态规划怎么做，实际上是由暴力递归的参数、条件得出来的。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7][]

最终得答案就是4。我们可以发现实际上这最后一行是没用的，每一个都一样，我们可以省略，第一排初始化得时候也都是1。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8][]

可以进一步优化，绿色节点实际是由两个黄色节点相加而成的，因为我们在计算dp\[0\]\[4\]的时候已经加过之前这个循环的节点方法数了，所以可以直接复用。代码如下：

所以代码如下：

public static int coins2(int[] arr, int aim){
            if (arr == null || arr.length == 0 || aim < 0) {
                return 0;
            }
            int[][] dp = new int[arr.length ][aim + 1];
            for (int i = 0; i < dp.length; i++) {
                dp[i][0] = 1;
            }
            for (int j = 0; j * arr[arr.length - 1] <= aim;j++){
                dp[arr.length - 1][j * arr[arr.length - 1]] = 1;
            }
            for(int i = arr.length - 2; i >= 0;i--){
                for(int j = 1;j <= aim ;j++){
                    dp[i][j] = dp[i + 1][j];
                    dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                }
            }
            return dp[0][aim];
        }

### 四、三种方法的时间比较 ###

public static void main(String[] args) {
            int[] coins = { 10, 5, 1, 25 };
            int aim = 2000;
    
            long start = 0;
            long end = 0;
            start = System.currentTimeMillis();
            System.out.println(coins1(coins, aim));
            end = System.currentTimeMillis();
            System.out.println("cost time : " + (end - start) + "(ms)");
    
            start = System.currentTimeMillis();
            System.out.println(getMap(coins, aim));
            end = System.currentTimeMillis();
            System.out.println("cost time : " + (end - start) + "(ms)");
    
    //        aim = 20000;
    
            start = System.currentTimeMillis();
            System.out.println(coins2(coins, aim));
            end = System.currentTimeMillis();
            System.out.println("cost time : " + (end - start) + "(ms)");
    
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9][]

动态规划的算法还是很优秀的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616210054367.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200616210146109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200616210304204.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200616210358871.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200616210744221.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200616211017782.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200616211348350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200616211548357.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200616211903357.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200616212115328.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70