动态规划学习

动态规划

本来想用5W2H分析法来解释此问题，但是发现比较困难，还是先看例子吧。
动态规划的原理：动态规划先解决子问题，再逐步解决大问题。先有这个简单的概念即可，我会通过例子来说明。

举例：做个小偷顾问

例1，打家劫舍（无限背包问题）

问题描述

在万恶的资本主义社会美国，有一个小偷（罗伯特），有一天晚上罗伯特与他的同伙开了一辆卡车（假如可以装无限的现金）来到了一排主人都出门旅游去了的房屋面前，每间房内都藏有一定的现金，影响罗伯特偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 请帮他设计程序以偷取最多的现金。

问题分析

1、简化问题

• 如果只有一个房子罗伯特最多能偷多少钱？
• 如果有两个房子罗伯特最多能偷多少钱？
• 如果有三个房子罗伯特最多能偷多少钱？
• 。。。。。。

为了方便分析，我们把房子的数量和能够偷的钱数记录下来，我们画一个表格如下：

• 第一列表示如果只偷前面的n个房子
• 第二列表示如果只偷前面的n个房子最多能偷多少钱
• 括号里面的是偷哪些房子

2、各个击破简化后的问题

如果只有前面一个房子罗伯特最多能偷多少钱？

房子数量	最多能偷多少钱？
1	$100(1)

如果只有前面两个房子罗伯特最多能偷多少钱？
当只有前面两个房子时，因为限制条件是不能偷相邻的房子不然会触发报警，所以偷其中金额大的那个即可。

房子数量	最多能偷多少钱？
1	$100(1)
2	$200(2)

如果只有前面三个房子罗伯特最多能偷多少钱？
当只有前面三个房子时，我们有两种选择，第1种：偷第三个和第一个；第2种：偷第二个。从两种选择中挑一个能偷的金额较大的方法。

房子数量	最多能偷多少钱？
1	$100(1)
2	$200(2)
3	$200(2)

如果只有前面四个房子罗伯特最多能偷多少钱？

当只有前面四个房子时，我们有两种选择：

• 第1种：偷第四个，再加上偷前两个房子的最大值
• 第2种：不偷第四个，只偷前面三个房子的最大值

从两种选择中挑一个能偷的金额较大的方法。

房子数量	最多能偷多少钱？
1	$100(1)
2	$200(2)
3	$200(2)
4	$500 = $300(4) + $200(2)

如果只有前面五个房子罗伯特最多能偷多少钱？
当只有前面五个房子时，我们有两种选择：

• 第1种：偷第五个，再加上偷前三个房子的最大值
• 第2种：不偷第五个，只偷前面四个房子的最大值

从两种选择中挑一个能偷的金额较大的方法。

房子数量	最多能偷多少钱？
1	$100(1)
2	$200(2)
3	$200(2)
4	$500 = $300(4) + $200(2)
5	$500 = $300(4) + $200(2)

3、总结归纳

我们通过上面的表格可以总结出来什么吗？我们在此约定一个数学公式：total(n)表示最大能偷的金额；使用amount(n)表示第n个房子有多少金额
根据以上的表格我们可以知道
total(1) = 100 = amount(1) = max(amount(1), 0)
total(2) = 200 = max(amount(2), amount(1))
total(3) = 200 = max(amount(3) + amount(1), amount(2)) = max(amount(3) + total(3-2), total(2))
total(4) = 500 = max(amount(4) + total(4-2), amount(3)) = max(amount(4) + total(4-2), total(3))
total(n) = max(amount(n) + total(n-2), total(n-1))

4、代码实现

经过上面的分析我们竟然总结出了一个公式：total(n) = max(amount(n) + total(n-2), total(n-1))
大家应该对斐波那契数列比较熟悉，他的公式是：f(n) = f(n-1) + f(n-2)，然后可能第一反应就想到了递归的实现，那么我们也可以使用递归的方式解决罗伯特的问题把？show you the code：

// 递归方式
public int robRecursion(int[] nums) {
    // 当没有房子时
    if (Objects.isNull(nums) || nums.length == 0) {
        return 0;
    } else if (nums.length == 1) {
        // 当只有一个房子时
        return nums[0];
    } else if (nums.length == 2) {
        // 当只有两个房子时
        return Math.max(nums[0], nums[1]);
    } else {
        // 其他情况
        // total(n) = max(amount(n) + total(n-2), total(n-1))
        return Math.max(nums[nums.length - 1] + robRecursion(Arrays.copyOf(nums, nums.length - 2)),
                robRecursion(Arrays.copyOf(nums, nums.length - 1)));
    }
}

OK，大功告成，上面的代码经过测试是没有问题的，解决了罗伯特的问题，回家睡觉。
等等！！！我们是不是忘了什么，这篇文章的标题不是动态规划吗，动态规划呢？
**
让我们再回头看一下递归的方式实现，每当要计算total(n)时，就先计算total(n-1)和total(n-2)，如果说我们先计算出来total(n-1)和total(n-2)是不是计算total(n)的时候就不用重新计算total(n-1)和total(n-2)了？按照这个思路我们就需要把每次计算出的total(n-1)和total(n-2)的结果记录下来，等计算total(n)的时候就可以直接用了。
show you the code：

// 动态规划方式
public int rob(int[] nums) {
    /*
     * 初始化动态规划的数组，此时的数组中的值都是0
     * 此数组的下标为偷取的前n个房屋的数量
     * 此数组的值为偷取的前n个房屋可以偷取的金钱最大值
     * 如果dp[5] = 100；表示偷取前面的5家房屋，最多可以偷取100刀
     */
    int[] dp = new int[nums.length + 1];
    for (int i = 1; i <= nums.length; i++) {
        int amountOfNumberI = nums[i - 1];
        // 如果只偷第一个房子
        if (i == 1) {
            dp[i] = amountOfNumberI;
        } else {
            /*
             * 此时有两种选择:1、偷当前的房屋；2、不偷当前的房屋，两种选择取最大值
             * 如果选择1，则要计算当前房屋的金钱与当前房屋前一个不相邻的所有房屋的金钱价值
             * 如果选择2，则直接取当前房屋之前的所有房屋能够偷的金钱最大值
             */
            dp[i] = Math.max(amountOfNumberI + dp[i - 2], dp[i - 1]);
        }
    }
    return dp[nums.length];
}

恭喜你，上面的代码就是动态规划的方式；与递归的方式不同，每次的计算结果都保存在了dp数组中，计算下一个值时直接从数组中获取以前计算过的值即可。罗伯特偷一排房子的源码

例2，背包问题

问题描述

有一天罗伯特带着一个可以装4kg的背包，去了一家小商店，小商店里面有下面至少三个商品；请帮助他决定应该偷哪些商品。

商品名称	商品价格（单位$）	商品重量（单位kg）
吉他	1500	1
音箱	3000	4
电脑	2000	3
…	…	…

问题分析

首先拿到这个问题可能一眼就看出来了答案，就是偷吉他和电脑；那么如果说商品数量是100个的话是无法一眼看出答案的，那么我们应该怎么去帮罗伯特决策呢？


我们再来看一下问题的关键：

• 容量4kg的背包
• 至少三个不同价格和不同重量的商品
• 一个商品要嘛全偷要嘛不偷，不能只偷一部分
• 偷的商品列表背包必须能装的下，并且价格最大

1、简化问题

简化问题的过程：

• 最简单的是什么？只有一个商品，只能装1kg的背包
• 增加点难度，只有一个商品，背包的重量逐渐增加到罗伯特的背包重量
• 继续增加难度，只有两个商品，1kg的背包能偷什么？2kg的背包能偷什么？3kg、4kg呢？
• 有三个商品，1kg的背包能偷什么？2kg的背包能偷什么？3kg、4kg呢？
• 有n个商品和能装mkg的背包

2、简化后的问题各个击破

把问题最小化：只有一个商品，只能装1kg的背包

到这里其实我们还是无法知道到底应该怎么帮罗伯特决策，那么我们可不可以把问题简化一下，假如背包容量是1，商品个数也是1只有一把吉他；如下：

• 容量1kg的背包
• 1把重量是1kg价格是$1500的吉他

如果是上面简化后的问题，我们是可以计算的，计算方法是：判断吉他能否装入背包，如果可以则1kg容量的背包可以偷吉他，最大价格是$1500，我们继续使用一个表格把它记录下来：
我们先约定好表格的内容：

• 行表示背包的容量
• 列表示有哪些商品
• 单元格的数字表示可以偷的最大值
• 括号里面是偷哪些商品
  | 商品\容量 | 1 |
  | — | — |
  | 吉他 | 1500（吉他） |

我们是如何得到上面的表格的呢？判断吉他是否能装进容量为1kg的背包中，如果可以则偷吉他，吉他的价格也就是偷取的最大的价格。

增加难度，增加背包的容量：只有一个商品，背包的重量逐渐增加到罗伯特的背包重量

我们在上面的基础上再把背包的容量增加，直到增加到与罗伯特的背包相同的容量为止，但是依然只可以偷取一把吉他；我们把这些信息记录下来如下，其中第一列为商品，第一行为背包容量，表格记录的是偷取商品的最大价格，括号里面的是偷取的商品。
如下表的红色部分就代表，背包容量为4只有一把吉他可偷时，可以偷取的商品最大价格是1500，偷取的商品是吉他。

商品\容量	1	2	3	4
吉他	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）

继续增加难度，增加一个商品

我们再在上面的基础上，增加可以偷取的商品，再加一个音箱，然后使用相同的方法绘制上面的表格；

商品\容量	1	2	3	4
吉他	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）
音箱	1500（吉他）

上面可以看到**table[音箱][容量1]**的单元格的值如上表是1500,因为容量是1的背包无法装下音箱，所以依然只能偷吉他，所以可以偷取的商品的最大的价格为1500。
让我们完成这个表格的填写：

商品\容量	1	2	3	4
吉他	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）
音箱	1500（吉他）	1500（吉他）	1500（吉他）	3000（音箱）

如上表所示，当背包容量为4时，可以装下音箱，并且音箱的价格3000大于**table[吉他][容量4]的1500，所以此时我们设置table[音箱][容量4]的单元格的最大价格为3000。table[音箱][容量4] = Max(当前行计算的值, table[吉他][容量4])

继续增加难度，再增加一个商品再增加一个商品

我们继续把电脑增加到可以偷取的商品列表中，然后继续使用相同的方法画出电脑行的前三个容量的单元格如下：此时我们可以看到**table[电脑][容量3]**的值应该是2000，因为容量是3时可以装下电脑，而且电脑的价格比吉他的价格高，所以此时罗伯特应该偷电脑而不是吉他。

商品\容量	1	2	3	4
吉他	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）
音箱	1500（吉他）	1500（吉他）	1500（吉他）	3000（音箱）
电脑	1500（吉他）	1500（吉他）	2000（电脑）

table[电脑][容量3] = Max(当前行计算的值, table[音箱][容量3])
我们继续看最后一个单元格（**table[电脑][容量4]）**应该填什么，如果罗伯特偷电脑，则背包容量还剩下1，而容量为1的背包可以偷取的商品价格最大值是1500，偷取的商品是吉他，所以此时可以选择偷取电脑+吉他，价格是2000+1500=3500；这比之前记录的背包容量是4时的商品最大值（3000）大，所以这个单元格的价格应该是3500，偷取的商品是电脑+吉他

商品\容量	1	2	3	4
吉他	1500（吉他）	1500（吉他）	1500（吉他）	1500（吉他）
音箱	1500（吉他）	1500（吉他）	1500（吉他）	3000（音箱）
电脑	1500（吉他）	1500（吉他）	2000（电脑）	3500（电脑+吉他）

table[电脑][容量4] = Max(当前行计算的值 + 剩余容量可以偷取的最大值, table[音箱][容量3])
OK，完成上面的表格之后我们就可以确定，罗伯特应该偷电脑+吉他，商品的价格为3500。随着我们不断的填写表格，我们可以知道结果最终保存在表格的右下角，即**table[电脑][容量4]**的单元格内。

2、总结归纳

让我们总结一下每个单元格填写的规律：
假设背包总容量为V，商品的数量是M，第i个商品的重量是Wi，价格是Pi，容量是v（1<v<=V）时我们可以使用下面的公式：
f(i,v) = Wi <= v ? max(Pi + f(i-1, v-Wi), f(i-1, v)) : f(i-1, v)
分解上面的公式：

情形	值
Wi <= v	max(Pi + f(i-1, v-Wi), f(i-1, v))
Wi > v	f(i-1, v)

3、代码实现
我们继续用上面罗伯特打家劫舍的思路，把已经计算过的值保存下来，然后在用到的时候直接取用。因为当前问题有多个商品和多种背包容量两个限制纬度，所以在记录时需要用到二维数组。
show you the code：

    /**
     * 给出商品列表和背包的容量，请计算偷取哪些商品可以达到价格最大化，最大的价格是多少？
     *
     * @param products    商品列表
     * @param bagCapacity 背包容量
     * @return 能够偷取的商品最大的价格之和
     */
    public int stealMaxPrice(Product[] products, int bagCapacity) {
        /*
         * 二维数组，记录已经计算过的最大价格
         * 二维数组比商品的个数多1，比背包的大小多1，原因是为了方便使用相同的公式，第0行和第0列的值都是0
         */
        int[][] table = new int[products.length + 1][bagCapacity + 1];
        for (int j = 1; j <= products.length; j++) {
            Product product = products[j - 1];
            for (int currentBagCapacity = 1; currentBagCapacity <= bagCapacity; currentBagCapacity++) {
                table[j][currentBagCapacity] = product.weight <= currentBagCapacity ?
                        Math.max(product.price + table[j - 1][currentBagCapacity - product.weight], table[j - 1][currentBagCapacity])
                        : table[j - 1][currentBagCapacity];
            }
        }
        return table[products.length][bagCapacity];
    }

    /**
     * 商品信息
     */
    static class Product {
        public Product(String name, int price, int weight) {
            this.name = name;
            this.price = price;
            this.weight = weight;
        }

        /**
         * 商品名称
         */
        String name;
        /**
         * 商品价格(单位$)
         */
        int price;
        /**
         * 商品重量(单位磅)
         */
        int weight;
    }
}

代码中的table最终是这样的：

0	0	0	0	0	0
0	1500	1500	1500	1500	1500
0	1500	1500	1500	1500	3000
0	1500	1500	1500	2000	3500

其实上面的代码我简化了一下，返回的是最大能偷的价格，而罗伯特当然是要价格最大的商品列表了，这个实现比较麻烦不贴在这里了可以看源码

什么是动态规划（英语：Dynamic programming，简称DP）

概念：

动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

用途：

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

适用情况

• 最优子结构性质。
  • 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
  • 最优子结构性质为动态规划算法解决问题提供了重要线索。
• 无后效性。
  • 即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
• 子问题重叠性质。
  • 子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。
  • 动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

### 重叠子问题：如何理解这个概念呢？Fibnacci数列

public int fib(int n){
    assert n >=0;
    if(n<2){
        return n;
    }
    return fib(n-2) + fib(n-1);
}

在上面的斐波那契数列的递归的实现方法中，我们传入的参数n等于8或者等于10的时候，第m（m<n）个数字是变化的吗？

public int fib(int n) {
    assert n >= 0;
    int[] c = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        if (i < 2) {
            c[i] = i;
        } else {
            c[i] = c[i - 2] + c[i - 1];
        }
    }
    return c[n];
}

动态规划是递归算法的优化方案，一般来说能用递归的都可以思考一下能不能使用动态规划的方式优化。

最优子结构性质

上面两个罗伯特的例子就是最“优自结构性质”的问题，不好解释大家可以自己体会。

总结：判断是否可以用动态规划解决问题的核心是：大规模的问题是否能够通过较小规模的问题来解决。

效率：

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

一些可以使用动态规划解决的常见题目

• 爬楼梯问题
• 最长子串（子串需要连续）
• 最长子序列（子序列不需要连续）
• 最长子串的变种：最长回文子串（回文：“上海自来水来自海上”）
• DNA序列比对

动态规划不可以解决什么问题

• 可以拆分的商品（如罗伯特拿着4kg的背包偷四袋不同价格的豆子（这些商品可以拆分））