关键词：
前言
今天开始学习动态规划，一共有三节，分别是：初识动态规划、动态规划理论、动态规划实战。今天这一节就是初识动态规划。
动态规划比较适合用来求解最优问题，比如最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。
下面会通过两个非常经典的动态规划问题模型来展示为什么需要动态规划，以及动态规划解题方法是如何演化出来的。
0-1背包问题
对于一组不同重量、不同分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
这问题可以通过回溯算法来解决，代码如下：
public class Soluction
private int maxW = int.MinValue; // 结果
private int[] weight = new int[] 2, 2, 4, 6, 3 ; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包最大承受
public void F (int i, int cw)
if (cw == w || i == n) // cw==w表示背包满了，i==n表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
F (i + 1, cw); // 选择不装第i个物品
if (cw + weight[i] <= w)
F (i + 1, cw + weight[i]); // 选择装第i个物品
public int GetResult ()
return maxW;
回溯算法可以通过递归树来分析，如下图：
通过递归树可计算回溯算法的时间复杂度，时间复杂度是指数级的(O(2^n))，非常高。
通过递归树可知，回溯算法中存在大量的重复计算，这个可以通过“备忘录”的方法来优化，优化后的代码如下：
// 回溯算法优化，增加“备忘录”
public class Soluction2
private int maxW = int.MinValue; // 结果
private int[] weight = new int[] 2, 2, 4, 6, 3 ; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包最大承受
private bool[][] mem = new bool[5][]; // 备忘录，默认值false
public Soluction2 ()
for (int i = 0; i < 5; i++)
mem[i] = new bool[10];
public void F (int i, int cw)
if (cw == w || i == n) // cw==w表示背包满了，i==n表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
if (mem[i][cw]) return; // 重复状态
F (i + 1, cw); // 选择不装第i个物品
if (cw + weight[i] <= w)
F (i + 1, cw + weight[i]); // 选择装第i个物品
public int GetResult ()
return maxW;
下面我们来看一下动态规划是如何解决这个问题的。
- 把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。
- 把每一层重复的状态合并，只记录不同的状态，然后基于上一层的状态集合来推导下一层的状态集合。
- 以此类推，直到考察完所有物品。只需要在最后一层，找一个值为true的最接近w的值，就是背包中物品总重量的最大值。
整个过程如下图：
翻译成代码如下：
public int Knapsack (int[] weight, int n, int w)
bool[][] states = new bool[n][]; // 默认值false
for (int i = 0; i < n; i++) states[i] = new bool[w + 1];
states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
if (weight[0] <= w) states[0][weight[0]] = true;
for (int i = 1; i < n; i++) // 动态规划状态转移
for (int j = 0; j <= w; j++) // 不把第i个物品放入背包，则把上一轮的状态移下来
if (states[i - 1][j]) states[i][j] = states[i - 1][j];
for (int j = 0; j <= w - weight[i]; j++) // 放第i个物品，在不超出背包最大承重w的范围内，再判断上一轮的状态，来设置
if (states[i - 1][j]) states[i][j + weight[i]] = true;
for (int i = w; i >= 0; i--) // 从最后一行（下标n-1）找到值为true的位置，即为结果
if (states[n - 1][i]) return i;
return 0;
这个代码的时间复杂度是O(n * w)，其中n表示物品个数，w表示背包可以承载的总重量。空间复杂度也是O(n * w)，使用了个二维数组来保存状态。
实际上空间复杂度可以进一步代码，只需要w + 1的空间即可。代码优化如下：
public int Knapsack2 (int[] weight, int n, int w)
bool[] states = new bool[w + 1];
states[0] = true;
if (weight[0] <= w) states[weight[0]] = true;
// 对比上面的代码，主要是不再保存每一轮的状态，而是合并保存状态。
for (int i = 1; i < n; i++)
for (int j = w - weight[i]; j >= 0; --j) // 对比上面的代码，这里是从大到小遍历，目的是为了避免状态的修改，影响后续的结果。
if (states[j]) states[j + weight[i]] = true;
for (int i = w; i >= 0; --i)
if (states[i]) return i;
return 0;
对比上面的代码，上面代码是保存每一轮的状态，而实际上这个问题只需要最后一轮的状态即可。但是要注意第8行代码，j是从大到小遍历的，这里主要是因为只有一轮状态保存，为了不影响其他状态。
0-1背包问题升级版
刚刚的背包只涉及背包重量和物品重量，我们改造一下刚刚的背包问题，引入物品价值这一变量。
对于一组不同重量、不同价值、不可分割的物品，选择将某些物品装入背包，在满足背包最大重量的限制的前提下，背包中可装入物品的总价值最大是多少？
这个问题依旧可以使用回溯算法来解决，但是就没办法通过备忘录来优化了。
我们来看一下动态规划如何解决这个问题，直接上代码：
public int Knapsack3 (int[] weight, int[] value, int n, int w)
int[][] states = new int[n][];
for (int i = 0; i < n; i++) states[i] = new int[w + 1];
states[0][0] = 0;
if (weight[0] <= w) states[0][weight[0]] = value[0];
for (int i = 1; i < n; i++)
for (int j = 0; j <= w; j++) // 不放第i个物品
if (states[i - 1][j] > 0) states[i][j] = states[i - 1][j];
for (int j = 0; j <= w - weight[i]; j++) // 放第i个物品
if (states[i - 1][j] > 0) states[i][j + weight[i]] = states[i - 1][j] + value[i];
for (int i = w; i >= 0; i--) if (states[n - 1][i] > 0) return states[n - 1][i];
return 0;
时间复杂度和空间复杂度一样是O(n * w)。同理，一样可以优化空间，代码如下：
public int Knapsack4 (int[] weight, int[] value, int n, int w)
int[] states = new int[w + 1];
states[0] = 0;
if (weight[0] <= w) states[weight[0]] = value[0];
for (int i = 1; i < n; i++)
for (int j = w - weight[i]; j >= 0; j--) // 放第i个物品
if (states[j] > 0) states[j + weight[i]] = states[j] + value[i];
for (int i = w; i >= 0; i--)
if (states[i] > 0) return states[i];
return 0;
案例：如何巧妙解决“双十一”购物时的凑单问题
淘宝的“双十一”购物节有各种促销活动，比如“满200减50”。假设你女朋友的购物车中有n个（n>100)想买的商品，她希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件（200元）。
直接上代码：
public class Soluction4
// items商品价格，n商品个数, w表示满减条件，比如200
public void Double11advance (int[] items, int n, int w)
int[][] states = new int[n][];
for (int i = 0; i < n; i++)
states[i] = new int[3 * w + 1];
states[0][0] = 0;
if (items[0] <= 3 * w) states[0][items[0]] = items[0];
for (int i = 1; i < n; i++)
for (int j = 0; j <= 3 * w; j++) // 不放第i个物品
if (states[i - 1][j] > 0) states[i][j] = states[i - 1][j];
for (int j = 0; j <= 3 * w - items[i]; j++) // 放第i个物品
if (states[i - 1][j] > 0) states[i][j + items[i]] = states[i - 1][j] + items[i];
int maxW = 0; // 找出大于等于w的最小值
for (maxW = w; maxW < 3 * w + 1; ++maxW)
if (states[n - 1][maxW] > 0) break;
if (maxW == 3 * w + 1) return; // 没有可行解
Console.WriteLine ($"w的最小值：maxW");
Console.Write ("购买组合：");
for (int i = n - 1; i >= 1; --i) // i表示二维数组中的行，j表示列
if (maxW - items[i] >= 0 && states[i - 1][maxW - items[i]] > 0) // states[i][j]有值，要么是不购买i,
Console.Write (items[i] + " "); // 购买这个商品
maxW = maxW - items[i];
// else 没有购买这个商品，j不变。
if (maxW != 0) Console.Write (items[0]);
class Program
static void Main (string[] args)
Soluction4 soluction = new Soluction4 ();
soluction.Double11advance (new int[] 15, 93, 23, 843, 74, 82, 39, 46, 5, 26, 32, 37 , 12, 200);
输出结果是：37 32 26 5 46 39 15
上面的代码有一点要注意的，如何根据状态集合来判断是否购买此商品。
状态(i, j)只有可能从(i - 1, j)或者(i - 1, j - value[i])两个状态推导出来。所以就检查这两个状态是否可达的，也就是states[i - 1][j]或者states[i - 1][j - value[i]]是否为true。
如果states[i - 1][j]可达，就说明我们没有选择购买第i个商品，如果states[i - 1][j - value[i]]可达，那就说明我们选择了购买第i个商品。
参考资料
c++不知算法系列之初识动态规划算法思想(代码片段)
1.概述动态规划算法应用非常之广泛。对于算法学习者而言，不跨过动态规划这道门，不算真正了解算法。初接触动态规划者，理解其思想精髓会存在一定的难度，本文将通过一个案例，抽丝剥茧般和大家聊聊动态规划。动态规... 查看详情
java入门算法（动态规划篇1：初识动规）
....Java入门算法（双指针篇）丨蓄力计划六.Java入门算法（数据结构篇）丨蓄力计划 查看详情
数据结构与算法--动态规划算法(代码片段)
1、0-1背包问题//0-1背包问题--动态规划算法publicclassDynamicPlanpublicstaticvoidmain(String[]args)DynamicPlandynamicplan=newDynamicPlan();int[]weight=1,2,3,4,5;System.out.println("方法一背包所装物品的重量为："+dynamicplan.knap 查看详情
数据结构与算法三个经典案例带你了解动态规划(代码片段)
本系列文章【数据结构与算法】所有完整代码已上传github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接https://github.com/Lpyexplore/structureAndAlgorithm-JS我们在面对很多问题时，会通... 查看详情
数据结构与算法学习——动态规划-1
数据结构与算法学习——动态规划-1目录目录博主介绍动态规划1.1、概念说明1.2、使用最小花费爬楼梯2.3、不同路径2.4、不同路径II2.5、整数拆分2.6、不同的二叉搜索树2.7、分割等和子集2.8、最后一块石头的重量II2.9、最长递增子... 查看详情
对动态规划算法的理解及相关题目分析(代码片段)
1、对动态规划算法的理解（1）基本思想：动态规划算法的基本思想与分治法类似：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。但是，与分治法不同的是，为了避免重复多次... 查看详情
数据结构与算法——动态规划
简介动态规划有时被认为是与递归相反的算法。递归是从问题的顶部开始，将一个完整的问题一步步分解成一个个子问题，通过解决掉所有分解出来的这些子问题的方式，来解决整个问题。动态规划是从问题的底部开... 查看详情
数据结构与算法学习——动态规划-2
数据结构与算法学习——动态规划-2目录博主介绍前言1、最长连续递增序列1.1、最长重复子数组1.2、最长公共子序列1.3、不相交的线1.4、最大子序和1.5、判断子序列1.6、不同的子序列1.7、两个字符串的删除操作1.8、编辑距离1.9、... 查看详情
动态规划电路布线问题(代码片段)
算法笔记——【动态规划】电路布线问题原创 2013年03月14日09:18:27标签：电路布线 /算法笔记 /动态规划 /最优子结构12785 1、问题描述： 在一块电路板的上、下两端... 查看详情
《数据结构与算法之美》22——递归树(代码片段)
前言在排序那一节里，讲到排序时，利用递推公式推导时间复杂度来求解归并排序、快速排序的时间复杂度，但有些情况，例如快速排序的平均时间复杂度，利用递推公式，会涉及很复杂的数据推导。今天学习一种特殊的树来分... 查看详情
数据结构与算法学习——动态规划-3
数据结构与算法学习——动态规划-3目录博主介绍前言1、礼物的最大价值1.2、最长不含重复字符的子字符串1.3、把数字翻译成字符串1.4、删除并获得点数1.5、接雨水1.6、丑数II1.7、跳跃游戏I1.8、跳跃游戏II1.9、环形子数组的最大... 查看详情
算法设计与分析之动态规划
今天刚刚学了动态规划，把书上的代码敲了一下，在此留下一笔。动态规划与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。在子问题的求解过程中，有... 查看详情
初识动态规划
1.能用动态规划解决的问题的特点： 1）问题具有最有子结构性质。如果问题的最优解包含的子问题的解也是最优的，就称该问题有最优子结构性质 2）无后效性。当前的若干状态值一旦确定，则此后过程的演变就之和这... 查看详情
数据结构与算法之美-堆和堆排序(代码片段)
堆和堆排序如何理解堆堆是一种特殊的树，只要满足以下两点，这个树就是一个堆。①完全二叉树，完全二叉树要求除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。②树中每一个结点的值都必须大于等... 查看详情
动态规划与背包问题(代码片段)
...量不超出要求装入的物品不能重复 动态规划算法介绍动态规划(DynamicProgramming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法动态规划算法与分治算法类似，其基本思想也是... 查看详情
[动态规划与回溯算法]斐波那契数列与变形(代码片段)
大家好这是我的一个新的专题，动态规划，这里有我大量学习DP（动归）的学习笔记，和我的见解，但是博主在这一块一个是一个小白，还在摸索如果有我那里有错误，或者有更好的思路请你在评论... 查看详情
数据结构与算法简记--动态规划理论(代码片段)
动态规划理论一个模型三个特征多阶段决策最优解模型最优子结构最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我... 查看详情
动态规划算法学习(代码片段)
...解时，称该问题具有最优子结构。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而... 查看详情