40 | 初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？
王争
该思维导图由 AI 生成，仅供参考
淘宝的“双十一”购物节有各种促销活动，比如“满 200 元减 50 元”。假设你女朋友的购物车中有 n 个（n>100）想买的商品，她希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件（200 元），这样就可以极大限度地“薅羊毛”。作为程序员的你，能不能编个代码来帮她搞定呢？
要想高效地解决这个问题，就要用到我们今天讲的动态规划（Dynamic Programming）。
动态规划学习路线
动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。不过，它也是出了名的难学。它的主要学习难点跟递归类似，那就是，求解问题的过程不太符合人类常规的思维方式。对于新手来说，要想入门确实不容易。不过，等你掌握了之后，你会发现，实际上并没有想象中那么难。
为了让你更容易理解动态规划，我分了三节给你讲解。这三节分别是，初识动态规划、动态规划理论、动态规划实战。
第一节，我会通过两个非常经典的动态规划问题模型，向你展示我们为什么需要动态规划，以及动态规划解题方法是如何演化出来的。实际上，你只要掌握了这两个例子的解决思路，对于其他很多动态规划问题，你都可以套用类似的思路来解决。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文以“双十一”购物凑单问题为切入点，引出了动态规划的应用场景，并通过学习路线的分节介绍，帮助读者快速入门动态规划算法思想。文章分为三节，分别介绍了初识动态规划、动态规划理论和动态规划实战。通过两个经典的动态规划问题模型，读者可以了解动态规划的解题思路，并掌握类似问题的解决方法。在第二节中，作者总结了动态规划适合解决的问题特征，并对比了贪心、分治、回溯和动态规划这四种算法思想的特点和适用场景。最后一节则通过三个经典的动态规划问题实例，加深了读者对动态规划理论的理解。动态规划是一种用动态规划解决问题的思路，将问题分解为多个阶段，每个阶段对应一个决策，记录每一个阶段可达的状态集合，然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。文章还介绍了动态规划解决问题的时间复杂度和空间消耗，并提供了一维数组解决问题的代码实现。整体而言，本文通过生动的例子和清晰的代码实现，帮助读者深入理解动态规划算法思想，为解决类似问题提供了有力的工具和思路。文章内容涵盖了动态规划的基本概念、理论分析和实际应用，对读者快速了解动态规划算法具有重要指导意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(275)
- 最新
- 精选
P@tricK老师你这个只能精确到元，女朋友羊毛精说要求精确到0.01元，时间空间复杂度增大100倍🐶作者回复: 👍 说的没错
2018-12-261161
Monday1、这里我特别强调一下代码中的第 6 行，j 需要从大到小来处理。 这里自己写代码调试完才恍然大悟，第i轮循环中新设置的值会干扰到后面的设值。 2、特别感谢争哥今天让其他的课程的老师来客串了一节课，让我有了更多的时间学习本节。作者回复: 不着急你慢慢学就是了 不用非得跟的那么紧
2018-12-28527
阿崔cxr老师，这是我基于理解动态规划之后写出的优化版斐波那契数列，是否算是动态规划入门了 - - function faibonacci(n) { //可以基于动态规划的思想去优化 //存储每一个步骤的值，然后推导出之后的值 let hash = {}; const calcu = (n) => { if (n === 1 || n === 2) return 1; let a = hash[n - 1] || calcu(n - 1); let b = hash[n - 2] || calcu(n - 2); return a + b; } for (let i = 1; i <= n; i++) { hash[i] = calcu(i) } return hash[n] }作者回复: 👍 你还得把我文章里涉及的所有题目都搞明白、会默写才算入门呢
2019-02-15212
黄均鹏解开这道题的前提是首先得先有个女朋友作者回复: 男朋友也可以的：）
2019-02-25210
小虾米老师，倒数第二段的代码(背包升级版)的12行的if条件判断是不是写错了作者回复: 是的 我改下
2018-12-2610
blacknhole有个疑问： 解答开篇的示例代码中，for (int j = 0; j <= w; ++j) {...} 和 for (int j = 0; j <= w-items[i]; ++j) {...} 的循环条件是不是有问题啊，应分别为 j <= 3 * w 和 j <= 3 * w - items[i] 吧？作者回复: 是的 我改下 感谢
2018-12-263
草长莺飞老师这是我看了你的思路后自己写的代码，后面看了你的代码。有个地方就是放置与不放的地方就可以写在一个for循环中为什么要写两个for循环呢作者回复: 你说的哪个代码啊？
2019-03-2922
青青子衿杨辉三角的题目是不是可以这样想，顶层最短路径=顶层节点值+第二层最短路径的最小值，依次类推，使用递归方法？如果这样做的话这个算法到底是分治算法还是动态规划算法？作者回复: 貌似不行，你这个算法本身就不对，你这个是贪心，而且没法求最优解
2019-08-0921
挠头侠老师 您给的github上的python01背包动态回归的代码 我将您背包升级问题的重量和价值导入，输出的最大价值不应该是18吗，可是给出的代码输出是17是不是有误呀。作者回复: 我去看下 多谢指出
2019-04-021
(Kelen)递归树那个图说法是不是由点问题啊，f(2,2)，代表应该是如果决定第二个放进去，2是放入的后的重量，而不是文中的放入前的重量作者回复: 好像没问题的。递归树和后面的递推公式你要分开看，并不是很一致。
2019-10-01
收起评论
