问题引入
问题引入小 Q 是一个宝石爱好者。这一天，小 Q 来到了宝石古董店，店家觉得小 Q 是个宝石行家，于是决定和小 Q 玩一个游戏。游戏是这样的，一共有 块宝石，每块宝石在小 Q 心中都有其对应的价值。注意，由于某些宝石质量过于差劲，因此存在只有店家倒贴钱，小 Q 才愿意带走的宝石，即价值可以为负数。小 Q 可以免费带走一个连续区间中的宝石，比如区间 或区间 中的宝石。请问小 Q 能带走的最大价值是多少？
问题分析
首先思考最暴力的解法。
枚举所有区间，暴力累加区间中宝石的价值，最后选一个价值最大的区间。时间复杂度O(n^3)。
O(n^3)显然有些无法接受，因此想想有没有办法优化，比如优化
优化 1.0
仔细思考不难发现，我们可以枚举区间右端点，然后固定右端点，左端点不断向左移动，边移动边累加，就可以将时间复杂度优化到O(n^2)。
例如我们固定右端点是 3，那么左端点就从 3 移动到 1，边移动边累加答案，就可以在移动过程中计算出区间[3,3]、[2,3]、[1,3]的答案了。因此枚举所有区间右端点，即可在 时间复杂度内找到答案。但是O(n^2) 时间还是有些过高了，因此思考有没有办法继续优化呢？
优化 2.0
观察O(n^2)的解法，不难发现我们用了O(n) 的时间复杂度才求出了固定某个点为区间右端点时，区间最大价值和。
例如固定了n为区间右端点后，我们通过从n到1枚举左端点，才求出了以n为区间右端点时的区间最大价值和，即O(n)的时间复杂度。
那么继续思考，「以n为区间右端点的区间最大和」，与「以n-1为区间右端点的区间最大和」，这两者是否有关联呢？
为了描述方便，接下来我们用f[i]来代替「以i为区间右端点的区间最大和」，用a[i]来代替第i块宝石的价值。不难发现，如果f[n-1]为正数，则f[n]一定等于f[n-1]+a[n]；如果f[n-1]为负数，则f[n]一定等于a[n]。
因此我们可以推导出如下转移方程：根据上述转移方程，我们可以在O(n)时间复杂度内求出最大的f[i]，即将此题时间复杂度优化到 ，而这个优化的过程就是「动态规划」的过程。
在上述推导过程中，一共分为两步：
- 将整个问题划分为一个个子问题，并令
f[i]为第i个子问题的答案 - 思考大规模的子问题如何从小规模的子问题推导而来，即如何
f[i-1]推出f[i]这两个步骤便是「动态规划」解题思路的核心所在，即确定动态规划时的「状态」与「转移方程」。
动态规划解题思路
动态规划主要分为两个核心部分，一是确定 「DP 状态」，二是确定 「DP 转移方程」。
DP 状态
「DP 状态」的确定主要有两大原则：
1. 最优子结构
我们仍以「宝石挑选」例题来讲解这两大原则，首先是「最优子结构」。
什么是「最优子结构」？将原有问题化分为一个个子问题，即为子结构。而对于每一个子问题，其最优值均由「更小规模的子问题的最优值」推导而来，即为最优子结构。
因此「DP 状态」设置之前，需要将原有问题划分为一个个子问题，且需要确保子问题的最优值由「更小规模子问题的最优值」推出，此时子问题的最优值即为「DP 状态」的定义。
例如在「宝石挑选」例题中，原有问题是「最大连续区间和」，子问题是「以i为右端点的连续区间和」。并且「以i为右端点的最大连续区间和」由「以i-1为右端点的最大连续区间和」推出，此时后者即为更小规模的子问题，因此满足「最优子结构」原则。由此我们才定义 DP 状态 f[i]表示子问题的最优值，即「以i为右端点的最大连续区间和」
2. 无后效性
而对于「无后效性」，顾名思义，就是我们只关心子问题的最优值，不关心子问题的最优值是怎么得到的。
仍以「宝石挑选」例题为例，我们令 DP 状态f[i]表示「以 i 为右端点的最大连续区间和」，我们只关心「以i为右端点的区间」这个子问题的最优值，并不关心这个子问题的最优值是从哪个其它子问题转移而来。
即无论f[i]所表示区间的左端点是什么，都不会影响后续 f[i+1]的取值。影响f[i+1]取值的只有f[i]的数值大小。
那怎样的状态定义算「有后效性」呢？
我们对「宝石挑选」例题增加一个限制，即小Q只能挑选长度<=k的连续区间。此时若我们定义f[i]表示「以i为右端点的长度<=k的最大连续区间和」，则f[i+1]的取值不仅取决于f[i] 的数值，还取决于f[i]是如何得到的。
因为如果f[i]取得最优值时区间长度=k ，则f[i+1]不能从f[i]转移得到，即f[i]的状态定义有后效性。
最后概括一下，「最优子结构」就是「DP状态最优值由更小规模的 DP 状态最优值推出」，此处 DP状态即为子问题。而「无后效性」就是「无论 DP状态是如何得到的，都不会影响后续 DP 状态的取值」。
转自知乎
