Part.I Introduction
刷题的时候一碰到动态规划的问题就头大，总觉得这类问题很复杂，给我一种不确定性，虚无缥缈，抓不住踩不实的感觉。于是在学习的过程中记了点笔记，后期整理才有了这篇博文。
因为并不是一气呵成的，时间跨度也比较大，所以文章的逻辑并不是很严密。
Chap.I Reference
Chap.II 基础概念
动态规划是由 Dynamic Programming (简称 DP) 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的，应用于工程领域。
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
下面是一些概念：
- 动态规划是求解多阶段决策过程(decision process)的最优化问题一种方法。所谓多阶段决策过程是指这样一类决策过程：它可以把一个复杂问题按时间(或空间)分成若干个阶段，每个阶段都需要作出决策，以便得到过程的最优结果。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的经济效果有关，还影响以后各阶段的经济效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法称为动态规划方法。然而，动态规划也可以处理一些本来与时间没有关系的静态模型，这只要在静态模型中人为地引入『时间』因素，分成时段，就可以把它看作是多阶段的动态模型，用动态规划方法去处理。
- 简言之，多阶段决策过程是指这样的一类特殊的活动过程：问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。
- 无后效性(without aftereffect)：无后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。利用动态规划方法求解多阶段决策过程问题，过程的状态必须具备无后效性（突然想到了马尔可夫性）。
- NP 完全问题 (Non-deterministic Polynomial Complete, NP-C 问题)：即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。想要彻底了解这个名词的含义首先需要知道下面的几个名词。
- P类问题 (polynomial)：所有可以在多项式时间内求解的判定问题构成 P 类问题。
- 判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。
- NP类问题 (Non-deterministic Polynomial)：所有的非确定性多项式时间可解的判定问题构成 NP 类问题。
- 非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。
- NPC问题：NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法，那么所有NP 问题都是多项式时间可解的。这些问题被称为NP-完全问题(NPC问题)。
Part.II 动态规划的思想
动态规划和分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法中分解得到的子问题不是互相独立的。若用分治法来解这类子问题，分解得到的子问题数目非常多，最后解决原问题需要耗费指数时间。
动态规划的核心思想：拆分子问题，记住过往，减少重复计算。
或者说，确定合适的状态，找出状态转移方程，自底而上地去『转移』。
状态：靠猜；状态转移要做到『不漏』或『不重不漏』，它可以用来检验状态的选取是否合适。
Chap.I 求解步骤
动态规划的求解步骤：
- 找出最优解的性质，并刻划其结构特征（确定状态量，一般靠经验）。
- 递归地定义最优值（构造状态转移方程）。
- 利用状态转移方程，自底而上计算出最优值，需要注意的是初值和特殊情况下的状态转移方程（根据题目需求，状态转移要做到『不漏』或『不重不漏』）。
- 根据计算最优值时得到的信息，构造最优解。
Chap.II 动态规划的一些属性
动态规划算法的基本要素：最优子结构、重叠子问题、状态转移方程。
最优子结构
- 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
- 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
- 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
- 注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
重叠子问题
- 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
- 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
- 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
状态转移方程
- 状态转移方程，顾名思义，就是从上一个状态转到下一个状态的转移方法。在实际问题中，状态转移方程往往是最难找的。
Chap.III 一些技巧
- 输入数组是否可以用来存储中间结果，这样就不用额外的内存开支了。
- 是否有必要存储所有的过往状态，有些问题往往只需要存储临近的两个或三个状态即可。
Part.III 具体实例
有许多类型的题都可以用动态规划的思想来解决，下面进行了一些总结。
因为笔者也是初学，以下内容暂时可能会比较简陋，笔者会不断更新的~
Chap.I 数塔问题
一般这种题比较简单，比如杨辉三角(帕斯卡三角)、斐波那契数列、
Chap.II 路径问题
这种题有一定的规律，掌握了一个题，所有的类似的题都迎刃而解了。
Chap.III 背包问题
常见的背包类型主要有以下几种：
- 1、0/1背包问题：每个元素最多选取一次
- 2、完全背包问题：每个元素可以重复选择
- 3、组合背包问题：背包中的物品要考虑顺序
- 4、分组背包问题：不止一个背包，需要遍历每个背包
而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
- 1、最值问题：要求最大值/最小值
- 2、存在问题：是否存在…………，满足…………
- 3、组合问题：求所有满足……的排列组合
下面是一些典型的背包问题
转载：https://blog.csdn.net/Gou_Hailong/article/details/127851294