动态规划中常见到的概念(1)子问题和原问题(2)状态(3)状态转移方程(4)DP数组(DP就是动态规划的缩写)动态规划的步骤(1)定义原问题和子问题(2)定义状态(3)寻找状态转移方程(4)编程实现实现方法1 自顶向下法2 自底向上法例题与代码实现礼物的最大价值问题叙述问题分析MATLAB代码实现
(Dynamic Programming简称DP)
动态规划是运筹学的一个分支，通常用来解决多阶段决策过程最优化问题。动态规划的基本想法就是将原问题转换为一系列相互联系的的子问题，然后通过逐层递推来求得最后的解。
动态规划中常见到的概念
(1)子问题和原问题
原问题就是你要求解的这个问题本身，子问题是和原问题相似但规模较小的问题
(原问题本身就是子问题的最复杂的情形，即子问题的特例)。
(2)状态
状态就是子问题中会变化的某个量，可以把状态看成我们要求解的问题的自变量。
(3)状态转移方程
能够表示状态之间转移关系的方程，一般利用关于状态的某个函数建立起来。
(4)DP数组(DP就是动态规划的缩写)
DP数组也可以叫”子问题数组”,因为DP数组中的每一个元素都对应一个子问题的结果，DP数组的下标一般就是该子问题对应的状态。
动态规划的步骤
一般会经历四个步骤
(1)定义原问题和子问题
子问题是和原问题相似但规模较小的问题。
(2)定义状态
这里的状态大家可以认为就是某个函数的自变量，根据状态中包含的参数个数的不同，我们在编程时设置的DP数组的维度就不同。每个状态中的参数通常都能对应DP数组中某个元素的下标，而DP数组的元素就是这个状态对应的子问题的求解结果。
(3)寻找状态转移方程
这一步往往是最难的，大家需要找到关于状态之间的某种转移关系，这个关系往往是一个递推式子，根据这个递推式我们才能一步一步计算出DP数组里面的元素。另外别忘了确定边界条件，也就是我们递推的初始条件。另外，如果一个问题能用动态规划方法求解，需要满足最优子结构和无后效性，我在讲解例题时回避掉了这一点，但这不代表它们并不重要，因为这一块的严格证明非常困难，后续如果你有兴趣可以学习专门的算法课程。
(4)编程实现
先初始化一个DP数组，再结合边界条件计算DP数组中的初始值，最后再利用循环来对DP数组进行迭代。一般DP数组中最后那个元素就是我们要解决的原问题的答案。
实现方法
动态规划通过组合子问题的解来求解原问题，一般来说，动态规划应用于重叠子问题的情况，即不同的子问题具有公共的子子问题。动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。
动态规划有两种等价的实现方法
1 自顶向下法
第一种方法称为带备忘的自顶向下法( top-down with memoization)。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的(memoized),因为它“记住"了之前已经计算出的结果。
2 自底向上法
第二种方法称为自底向上法(bottom-up method)。这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它(也是第一次遇到它)时，它的所有前提子问题都已求解完成。
例题与代码实现
礼物的最大价值
问题叙述
问题分析
MATLAB代码实现
函数准备
cumsum ：计算累积和（cumulative sum）
（1）如果 A 是一个向量，则 cumsum(A)可以计算向量 A 的累积和（累加值）。
A = [1 5 3 4 -5 0 8];
cumsum(A) % 计算 A 的累积和 | 1 6 9 13 8 8 16 |
（2）如果 A 是一个矩阵，则 cumsum(A,dim)可以计算 A 沿维度 dim 中所有元素的累积和，具体的使用方法和 sum 函数类似。
A = randi(10,3,4) | 4 6 6 8
7 4 3 3
8 2 1 5 |
% 计算每一列的累积和
cumsum(A) % 或者写成 cumsum(A,1) | 4 6 6 8
11 10 9 11
19 12 10 16 |
% 计算每一行的累积和cumsum(A,2) | 4 10 16 24
7 11 14 17
8 10 11 16 |
（3）也可以在最后加一个输入参数: 'omitnan', 这样计算时会忽略 NaN 值。
A = [5 3 -8 4
1 5 NaN 10;
3 6 18 9];
cumsum(A) % 计算每一列的累积和 |
5 3 -8 4
6 8 NaN 14
9 14 NaN 23 |
% 忽略 NaN 值计算每一列的累积和
cumsum(A,'omitnan') | 5 3 -8 4
6 8 -8 14
9 14 10 23 |
cumsum(A, 2) % 计算每一行的累积和 | 5 8 0 4
1 6 NaN NaN
3 9 27 36 |
% 忽略 NaN 值计算每一行的累积和
cumsum(A, 2, 'omitnan') | 5 8 0 4
1 6 6 16
3 9 27 36 |
主函数:
max_gift_value函数：
最后，动态规划问题需要多练，我这一讲涉及到的问题不算困难，只起到抛砖引玉的作用。大家真的对算法这一块感兴趣的话可以去B站搜索“数据结构”或者“算法”这种关键词，能学到很多计算机科班同学的课程。尽管在数模比赛中动态规划很少用到，但我相信大家学完这一节后思维一定很有启发，有兴趣的同学可以在“力扣"网站上面找到更多关于动态规划的练习题。