轻松学DP——动态规划 + 0-1背包

动态规划算法

精彩之处在后面，前面我们一定要用心理解理解这些文字表述的算法思想奥~

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到下一个更大的子问题解，这样一步一步扩大条件，直到达到原问题的条件，也就得到了原问题的解。

动态规划问题一般都是将问题描述成一个一维数组或者二维数组的方式，把目标的位置放在这个数组的最后一个位置。通过相当于填表的方式，一步一步扩大这个表格，直到从第一个位置走到最后一个位置，最后一个位置的状态就是这个问题的解。

动态规划具备了以下三个特点：

把原来的问题分解成了几个相似的子问题。
所有的子问题都只需要解决一次。
储存子问题的解。(提供给大问题用的)

动态规划的本质，是对问题状态的定义和状态转移方程的定义。(状态以及状态之间的递推关系)

动态规划问题一般从以下四个角度考虑：

状态定义
状态间的转移方程定义
状态的初始化
返回结果

状态的定义要求：定义的状态一定要形成递推关系， 这样才可以通过小的问题的解去推大问题的解嘛

适用场景：最大值/最小值, 可不可行, 是不是，方案个数

手把手练习

LeetCode139_字符串分割

在这里插入图片描述

怎么用动态规划算法解决这个问题，首先我们先想这个思想~

题目问你 “可不可以” 用词典的小字符串拼接成我们的大字符串，上面我们概括了动态规划的使用场景，这里这个 “可不可以” … 符合动态规划的场景！

然后我们再想：目前的状态是我们有一个字符串 s ，要找他从字典里被成功分词的子串，那，我们来想象一下：定义一个 i：他为 s 串的长度，定义一个 j：我们让 j < i；j>0，定义一个F(i) : i 长度串的状态，如果为 true，表示能被词典分割，为 false 则不能。

那么如果： F(j) == true && substring(j,i) 在词典中可以找到。也就是说，在 [0,i] 原本这个子串大小中，有一个长度小于 i 大小的下标为 j 的子串，这个子串的目前状态是能被词典分割，那么，如果 [j, i] 这一段小字符串也能在词典中找到，是不是就说明：F(i) = true。？？？？

顿悟了吗老铁，觉得能理解的点个赞呗~

话不多说上代码：要看一下代码里面的注解内容奥~ 每一个问题我们都尝试根据四个特点写出来状态递推

importjava.util.List;/*
    题目描述
    给定一个字符串s和一个词典wordDict，确定s是否可以根据词典中的词分成一个或多个单词。
    比如，
    给定 s = "leetcode"
    wordDict = ["leet", "code"]
    返回true，因为"leetcode"可以被分成"leet code"
*/publicclassLeetCode139_单词拆分 {/*
    状态：
        子状态：前1，2，3，...,n个字符能否根据词典中的词被成功分词
        F(i): 前i个字符能否根据词典中的词被成功分词
    状态递推：
        F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
        在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，
        则F(i)为true
    初始值：
        对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
        空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
        的例子进行验证
        F(0) = true
    返回结果：F(n)
    *///注意边界值问题，因为在字符串中存储是从0下标开始，而在数组中实际是从1开始、arr[0]为辅助--用来判断publicbooleanwordBreak(String s,List<String> dict){boolean[] canBreak =newboolean[s.length()+1];// 初始化F(0)=true
        canBreak[0]=true;for(int i =1; i <= s.length(); i++){// true{j < i && F(j) && substr[j+1,i]能在词典中找到}for(int j =0; j < i; j++){// F(j): 之前的字符串已经确定了可以有从集合中找到分割串的结果为true// 如果从[j+1, i]这个子串也在集合中，那么相对的 F(i) 就找到了结果，为trueif(canBreak[j]&& dict.contains(s.substring(j, i))){//substring左闭右开且字符向前挪一个// 通过前面已知的 F(j) 从小到大来求 F(i)
                    canBreak[i]=true;break;}}}return canBreak[s.length()];}}

LeetCode120_三角形最小路径和

在这里插入图片描述
这个问题我们来用两种方法递推：自顶向下、自底向上

开始喽~

三角形是数组形象化的表现，我们要做的是，

自顶向下：

从三角形的顶点走到底部，根据：

每一步只能移动到下一行的相邻节点(节点下标相同或者节点下标+1)

这个约束，走到底部的时候，找出一条路径最小的加和，返回这个最小和数。

这个问题的子问题要怎么来考虑的，即就是：我们的三角形有 n 层，最终也就是要从第 n 层这一层中找一个位置，从他走下来这条路径为加和最小值，全局最优解。那我们的局部最优解就可以往上那个看呀~ 第 n-1层，n-2层…第2层，当然，第 1 层只有一个数，这个数是必须要包括的。

分析完思想，我们来说做法：定义一个和原数组大小相同的二维数组，一层一层填充这个数组，从上往下，一层一层找路走，把以上的加和放在这个位置，

状态：

F(i,j) = Math.min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]

最后就从最后一层中返回一个位置为最小和的结果就好啦~

点个赞呗~

代码：

importjava.util.ArrayList;importjava.util.List;// 问题：从顶部到底部的最小路径和// 状态定义：从(0,0)到(i,j)的最小路径和// 状态转移方程：F(i,j)：Math.min(F(i-1,j),F(i-1,j-1)) + array[i][j]//            (j == 0 || j == i) : F(i,j)//                              j == 0: F(i-1,0) + array[i][0]//                              j == i: F(i-1,j-1) + array[i][j]// 状态初始化：F(0,0) = array[0][0]// 返回结果：Math.min(F(row-1,j)...)publicclassLeetCode120_三角形最小路径和 {publicintminimumTotal(List<List<Integer>> triangle){if(triangle.size()==0){return0;}List<List<Integer>> minPathSum =newArrayList<>();for(int i =0; i < triangle.size(); i++){
            minPathSum.add(newArrayList<>());}// F[0][0]初始化
        minPathSum.get(0).add(triangle.get(0).get(0));for(int i =1; i < triangle.size(); i++){int curSum =0;for(int j =0; j <= i; j++){if(j ==0){
                    curSum = minPathSum.get(i-1).get(0);}elseif(j == i){
                    curSum = minPathSum.get(i-1).get(j-1);}else{
                    curSum =Math.min(minPathSum.get(i-1).get(j-1),
                            minPathSum.get(i-1).get(j));}
                minPathSum.get(i).add(triangle.get(i).get(j)+ curSum);}}int size = triangle.size();int allMin = minPathSum.get(size-1).get(0);for(int i =1; i < size; i++){
            allMin =Math.min(allMin,minPathSum.get(size-1).get(i));}return allMin;}}

自底向上思想：这个更容易理解，看下面的注解就懂啦

// 自底向上// 状态F(i,j): 从(i,j)到达最后一行的最小路径和// 状态转移方程：//      F(i,j): min(F(i+1,j),F(i+1, j+1)) + array[i][j]// 初始状态：//      F(row - 1) = array[row-1][j]// 返回结果：//      F(0,0)publicintminimumTotal2(int[][] triangle){int row = triangle.length;for(int i = row-2; i >=0; i--){for(int j =0; j <= i; j++){
                triangle[i][j]=Math.min(triangle[i+1][j+1],triangle[i+1][j])+ triangle[i][j];}}return triangle[0][0];}

来两道练习题巩固一下吧：
LeetCode62_不同路径

LeetCode64_最小路径和

0-1 背包问题

背包问题可以通过动态规划算法来实现。

什么叫01背包问题？

背包问题通俗的说，就是假如你⾯前有3块宝⽯分别为a, b, c, 每块宝石的重量不同，并且每块宝石所带来的价值也不同（注意：这里宝石的重量的价值没有特定关系），目前我们有⼀个背包，只有固定的容量，要解决的问题就是在⼀定容量的背包⾯前装哪几块宝⽯才能获取到最大的价值，对于每块宝石我们只有拿或者不拿这两种选择，拿为1不拿为0，因此叫做0-1背包问题。

示例

有一个背包，其容量为 4 ，有三块宝石a，b，c，大小分别为：[1, 4, 3]；价值分别为：[15, 30, 20]，怎么装才能使得获取的价值最大？
宝石重量价值A115B430C320
⾸先对于我们人去操作而言，首先考虑应该是质量最轻，并且价值最大的，从数据中我们可以看到宝石c质量最小，且价值最大，应该优先考虑装这⼀块，然后依次考虑其他的。这种方式就是考虑性价比最高的宝⽯。我们可以将这个问题进⾏简化，目前是背包承重为4，因此，我们的选择较多，不知从何下⼿，那么我们假设背包的承重为3或者是2甚至是 1。在这种情况下，我们的选择就不多了，对于人类选择也是，在选择不多的情况下更容易找出最优方案，同样计算机也是。因此我们的背包问题也是从这开始，将选择较多的问题转化为选择不多的问题。在选择不多的情况下进行选择，有利于比较判断，依次递增， 最后解决背包承重为11的问题。

我们知道：对于背包问题，其实是⼀个动态规划，对于动态规划，⼤多数都是⽤⼀个数组来进⾏保存。那么我们来试着填充一下这个数组。

宝石0重量1的价值重量2的价值重量3的价值重量4的价值00000A015(a)15(a)15(a)15(a)B015(a)15(a)15(a)30(取a放b)C015(a)15(a)20(取a放c)35(a+c)
说明：
i：行坐标，代表宝石
j：列坐标，代表背包容量大小
v[i][j]：前 i 个宝石中能够装入容量为 j 的背包里的最大价值。

装入顺序从上到下、从左到右

填表过程：

v[i][0]：当容量为 0 时，价值为 0，所以这一列都为 0。
v[0][j]：不放宝石，价值为0。
接下来一行一行看，对于宝石a，他在容量为1，2，3，4的情况下，都可以放入，我们在第一行表中填入宝石a的价值。
再看宝石b，因为它的重量为4，所以在容量为1，2，3，的情况下它是放不下的，所以我们直接把上一行的价值拿下来，也就是此时包里装的是宝石a的价值。当容量为 4 时，可以放得下宝石b 了，但是因为包包里面此时有宝石a 占着空间，此时我们比较 [宝石a 的价值 < 宝石b 的价值] 就理所当然的取出a ，放入b，使价值最大。
最后我们放入宝石c，因为它的重量为3，所以在容量为1，2，的情况下它是放不下的，所以我们直接把上一行的价值拿下来，也就是此时包里装的是宝石a的价值。当容量为 3 时，可以放得下宝石b 了，但是因为包包里面此时有宝石a 占着空间，此时我们比较 [宝石a 的价值 < 宝石c 的价值] 就理所当然的取出a ，放入c，使价值最大，到容量为 4 时，背包此时还有剩余的空间大小为 1，它可以容纳宝石a，这时自然而然把宝石a 放入，此时背包内的总价值就为 35，也是最优解。

背包问题的思路：

背包问题主要是指⼀个给定容量的背包、若干具有⼀定价值和重量的物品，如何选择物品放入背包使物品的价值最大。这里的0-1背包是每个物品只能放一个，0→不放，1→放，求最大价值。

利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放⼊背包中。即对于给定的n个物品，设v[i]、w[i]
分别为第i个物品的价值和重量，C为背包的容量。
令v[i][j]表示在前 i 个物品中能够装入容量为j的背包中的最大价值。

可以推出：

v[i][0] = v[0][j] = 0 ，不放物品或者背包容量为0
当 w[i] > j 时：v[i][j] = v[i-1][j] ，物品重量大于当前最大容量，价值不会增加，填表时把上一行移下来就行。
**当 j > w[i] 时：v[i][j] = max(v[i-1][j]，v[i]+v[i][j-w[i]])**，就是比较之前不装入它的价值和为了装入它取出包内其他物品后的价值再加上它的价值的大的那一个值。 v[i-1][j]：就是上⼀个单元格的装入的最⼤值。 v[i]：表示当前要装⼊商品的价值。 v[i-1][j-w[i]] ：表⽰在前 i-1 个物品中能够装入容量为 j-w[i] 的背包中的最大价值。

做题巩固九章算法LintCode125