🔔 叮~
LeetBook 充电站今天要推荐的是一枚《 动态规划精讲（一）》，脑力值告急 ？一枚速食充电 ！
动态规划是求解多阶段决策过程最优化问题的方法，这里是 LeetBook 充电站推出的动态规划精讲系列的第二部！
点击标签栏里的 「LeetBook 充电站」 标签或点击头图，可以进入完整专栏
精准定位，对症下药，看你是哪一类 ？以下人群放心食用哦 ！
💡需充电症状人群：
- 需要掌握动态规划思想的同学
- 需要运用动态规划解决问题的学习者
- 线性、前缀和等动态规划的入门学习者
💎充电指南：
动态规划是通过把原问题分解为相对简单的子问题的方式求解复杂问题，最终获得最优解的算法。
常常被用在解决背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等问题中。也是面试常见考核算法类型。
本册 LeetBook 给大家体系化梳理知识点与题目，通过一题多解和多题一解两条学习路径，帮同学们快速找到所需的题目和知识点并系统学习！
本期充电站大家可以跟着力扣君一起来学习知识点，以及根据知识点有针对性地刷一些题目，巩固学习！
走，来不及解释了，快来充电！
今日电池 ——《 动态规划精讲（一） 》 共有五章，完成本 LeetBook 后，你将能够：
- 理解动态规划的基本思想
- 了解动态规划算法的优缺点和问题分类
- 掌握运用动态规划解决问题的思路
- 能够运用动态规划解决线性、前缀和、区间这三类问题
🎀 充电场景
我们来一起看看实际充电场景，充电 tips 请查收...
1. 充电同学 A：
“ 想知道动态规划与其他算法的关系 ！”
LeetBook 中第二章将会介绍分治和贪心算法的核心思想，并与动态规划算法进行比较。
小伙伴们快来跟上学习君的答疑解惑哦！
🎫 知识点来啦！
分治
解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。
举个栗子：例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。
这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。
贪心
- 关于最优子结构
- 贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
- 动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
- 关于子问题最优解组合成原问题最优解的组合方式
- 贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
- 动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
- 结果正确性
- 贪心不能保证求得的最后解是最佳的，复杂度低
- 动态规划本质是穷举法，可以保证结果是最佳的，复杂度高
在这一章你还可以了解到动态规划背景，以及解决动态规划问题的思考过程哦，点击下方文字来学习
💎学习指引：第二章 动态规划简介
2. 充电同学 B ：
“想了解下单串和双串，再来一点推荐题目！ ”
🎫 知识点+例题 套餐来啦！
单串
大部分的问题，对 i 位置的处理是第一种方式，例如力扣里这几道例题:
大家可以来做一做！看看自己理解了吗？
801 .使序列递增的最小交换次数
790. 多米诺和托米诺平铺
746 .使用最小花费爬楼梯
咱们继续回到 LeetBook 中，学习单串~
线性动态规划中单串 dp[i] 的问题，状态的推导方向以及推导公式如下：
单串 dp[i] 经典问题
以下内容将涉及到的知识点对应的典型问题进行讲解，题目和解法具有代表性，可以从一个问题推广到一类问题。
- 依赖比 i 小的 O(1) 个子问题
这个是单串 dp[i] 的问题，状态的推导方向，以及推导公式如下：
- 依赖比 i 小的 O(n) 个子问题
学完知识点记得来做题，LeetBook 每小节都根据知识点给出经典练习题！
快来第三章，继续学习单串，还有双串、矩阵等知识点！
💎学习指引：第三章 线性动态规划
3. 充电同学 C ：
“前缀和中的动态规划思想怎么理解 ？”
利用前缀和求区间和的思想，以及求前缀和的过程在上一节中已经重点介绍。
这里主要回顾一下前缀和中的动态规划思想，如下：
🎫 知识点+例题 来啦！
来看看题目吧！
上一节的最后提到前缀和可以推广到二维，解决的问题以及预处理时的算法思想与一维前缀和完全一样。
实现二维前缀和以及利用二维前缀和与数据结构的配合解决一些问题，本章后续节也有推荐题目哦！学习完了记得来几道题练练手！
进入下方学习指引，立刻 get 实现前缀和、数据结构维护前缀和问题、运算推广、差分等知识点！
💎学习指引：第四章 前缀和
📘 充电途径：
点击下方图片，即可进入学习
现可在《动态规划精讲（一）》中学习部分章节，喜欢就快加入书架吧！快速了 算法相关知识等知识，先溜了，去充电...
✨ 充电会员：
充电胖友 VIP 可立享精选学习资源免费阅读，《排序算法全解析》、《C++ 面试突击》..电量瞬间拉满，更多内容推荐欢迎关注下期充电站！
更多内容推荐欢迎关注下期充电站 ！
会员入口：
点击下方文字，即可进入会员专享
