动态规划
有个人想上一个n级的台阶，每次只能迈1级或者迈2级台阶，问：这个人有多少种方法可以把台阶走完？
相关问题：
（1）有个人想上一个n级的台阶，每次只能迈1级或者迈2级台阶，问：这个人有多少种方法可以把台阶走完？例如：总共3级台阶，可以先迈1级再迈2级，或者先迈2级再迈1级，或者迈3次1级总共3中方式。
（2）有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?
（3）一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
function taijie($num){
return $num<2?1:taijie($num-1)+taijie($num-2);
}
这里用的斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，
指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。
这个数列从第3项开始，每一项都等于前两项之和。
如何理解动态规划？
我觉得大部分高赞答案把简单的概念搞复杂了。
quora上有这样一个问题:
How should I explain dynamic programming to a 4-year-old?
底下有个42K赞同的答案，是这样说的：
*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*
"What's that equal to?"
*counting* "Eight!"
*writes down another "1+" on the left*
"What about that?"
*quickly* "Nine!"
"How'd you know it was nine so fast?"
"You just added one more"
"So you didn't need to recount because you remembered there were eight!Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"
就不翻译了，相信大家都能看懂。
按照定义，动态规划是把一个大问题拆解成一堆小问题，这个本身没啥问题，但是我觉得的这个不是动态规划的核心思想，或者说，一个”大问题“之所以能用”动态规划“解决，并不是因为它能拆解成一堆小问题，事实上啥大问题都能拆解成小问题...
取决于该问题是否能用动态规划解决的是这些”小问题“会不会被被重复调用。
举个例子，有n个阶梯，一个人每一步只能跨一个台阶或是两个台阶，问这个人一共有多少种走法？
首先要对这个问题进行抽象，n个阶梯，每个阶梯都代表一个”位置“， 就像是图论中的一个”点“，然后这些n个不同位置之间会有一些桥梁把它们连起来：
这个图，就是该问题的抽象表达形式，那么这个问题就转化成了从 Node 0 到 Node 10 有几种不同的路可以走？
其实这个就是问题的本质了。
那么如果我在计算出了从 5 到 10 的路径数，这个路径数是不是可以保存下来？
为什么要保存？因为这个信息一会儿还要再次被用到！
因为不管我是从3走过来的，还是从4走过来的，走到5之后，存在的路径就是第一次计算出的结果，你无需重复计算！
如果是暴力遍历的话，从 3 到 10 的时候， 你肯定会把 5 - 10 的可能路径数都算一遍，然后从 4 到 10 的时候，你又会把 5 - 10的路径算一遍，也就是重复计算了~
那么既然这样，我们创建一个数组a[]，专门来存放位点 x 到 10 的所有可能路径数，初始值记为 0，然后每当要计算 x 到 10 的路径数时，先检测一下该路径数的值是不是大于 0 ，如果大于，就说明它之前已经被计算过，并存在了a[x]中了!
那么我们马上可以得到一个递推关系:
a[x] = a[x+1] + a[x+2];
那么举个例子:
a[6] = a[7] + a[8];
a[7] = a[8] + a[9];
我们发现, 在计算 a[6] 和 a[7] 的时候, 我们都用了a[8]，也就是被重复利用了结果。
>欢迎大家参加我的Live, 本次Live将与大家一同探讨编程学习之最优方案
2 人已赞赏
个人觉得是因为这个名字非常让人困惑。英文dynamic programming，中文动态规划，给人一种很宏大的感觉。但其实对所谓动态和规划都没有那么深的体现，可以简单得理解为是对传统递归的一种优化。
Bellman，也就是”发明"了DP的人，自己说这个名字是他“编的”，主要为了规避军方的厌恶，否则就要用什么decision research这种名字了。(wiki:
Dynamic programming)
Bellman是个数学家，这里programming不是编程的意思，而是决策。但这种决策不是一下就出来的，而是一步步(multistage)积累出来。换句话说我们需要一个决策，但这个决策太大了，我们做不了，所以需要把他递归到我们可以简单做出决策的状态，然后从这些状态开始，慢慢的“动态地”演进到最终的决策。
比如说用最少的硬币换零钱，突然和你说要换78分钱，你怎么就能迅速给出答案呢，你不能。但是如果是1分的话，你就可以，2分的话呢，就是在1分的基础上再加1分，你也可以。于是你就慢慢地从1分开始一直算到78就有答案了。从另一个角度说，如果你用DP算出了怎么换78分，那如果我问你76分怎么换，你也应该有答案了。
所以在DP的实践中很重要的就是递推关系和边界条件。所谓边界条件就是最简单的情况，所谓递推关系就是如果你已经知道这么多，再多给你一个，你怎么得到。
说一个最最最简单的例子，找出一个数组中的最大值。这个问题边界条件是什么呢，就是如果只有一个元素，那最大值就是他；递推关系是什么，就是你已经知道当下最大的数，再多给你一个数你怎么办。你会拿这个数和当下最大的数去比，其中较大的那个就是新的最大的数。这就是典型dp的思想。所以不要把DP看的过于高深就好了。
-------
Bellman对DP名字的起源，自己在他的自传“Eye of the Hurricane: An Autobiography"中写了这样一段话，有兴趣的可以看一下：（原版第159页）
An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.
如果楼主不是为了竞赛刷题，可以先抛开书本上的什么状态转移方程什么的，可以教你一个民科点的思路O(∩_∩)O：
我们面对的是一个求最优解或统计之类的问题，这个问题基于“我们要模拟完成一个大任务”，这个大任务可以分成若干步骤，每个步骤有若干种决策，每个步骤完成后，就到达了一个阶段性状态
比如，你要从A地到Z地，没有直达，所以第一步需要到一个中间地点，比如H或I，第二步再前进，比如到P或Q，最后到达Z，每一步有若干决策，比如第一步你可以决定到H或I的中的某个，大致就是这样一个模型，可以自己画个地图看看
等等，你大概发现问题了，如果第一步到H和I都可以，第二步到P和Q都可以，那我每一步只选最优，不就用贪心得到结果了吗，没错，如果你需要经历的每个阶段状态跟决策无关，那就贪心得到结果好了，理解贪心了吗：）
然而现实情况可能是，你第一步的选择会影响后面的分支，比如你第一步可以选择到H或I，但是到了H后，你只能选择经过P或Q到Z了，而如果到了I，你只能选择R或S到Z，这样一来，即便第一步到H或I你选择了较好的一条路，也不保证最终结果最优，因为比如你选了H，那万一I-R-Z的路要比H开始到Z的路径短了更多，最优路径可能是A-I-R-Z，所以你要把这些路都尝试一遍，才知道哪个最优，理解穷举了么？：）
OK，我们稍微改下题设，假如从I出发不是到R和S，而是到Q或R，会如何
诚然，我们可以用穷举每条路来解决这个问题，需要穷举的路径数和上面的图一样，但是，我们可以有更快的办法，你不用将A-H-Q-Z和A-I-Q-Z两条路单独计算，因为他们有状态交点，结合第一张图的思想，可以敏锐地感觉到，我们只需要计算到每个有共同状态的位置求各阶段的最优，最后每阶段选最优组合贪心组合起来就行，因为各阶段完成的状态点是大家都有的嘛，因此，咱们先计算A-H-Q和A-I-Q，选个最好的，然后跟Q到Z中最好的拼起来，就是最优了，没必要把所有路径都搞一遍（虽然图里面Q到Z直达，但你可以发挥想象力，将其想象成各种分支的一条复杂道路），这样一来就把一个x^(a+b+c+...)的计算次数降低为x^a+x^b+x^c...，其中x代表每次的决策次数（简单点假设每次决策次数都一样），abc代表每个阶段的步骤数
因此，我们可以从A开始，向Z进行BFS，并对BFS中每个点保存最优状态，如果有不同的路径BFS到了同一个点，留最好的一条就行，比如上面这个，你的算法可能先从A-H-Q搜到了Q这个位置，之后从A-I-Q又到了这里，留最好的一条，最后一轮从PQR三个点到Z，就结束了，相对第二章图要少一次运算
如果你理解了，恭喜你已经能有效解决很多需要DP的问题了，同时还学会了解图论的单源最短路径问题呢
最后用经典的0-1背包问题做个例子，巩固一下吧，这个任务是，我们从N个物品选若干塞到可以承受最大重量W的包包里面，要价值最大，因此就可以将任务分成N个步骤，每个步骤面对第i号物品，决策有两条：选，还是放弃，这里的状态，就是影响之后步骤决策的因素，在这里，就是“背包的剩余空间”
比如，物品的重量是1,2,3,4,5,6，W=12，从头决策，0表示放弃，1表示选，BFS三次后有八种状态：
000 剩12
001 剩9
……（略）
110 剩9
……（略）
前三次步骤后，001和110到达了同样的状态，都是剩余可装重量9的东西，这样在剩下的决策中，这俩分支走的路都是一样的，跟你之前是选了001还是110没有任何关系（无后效性），因此只要看001价值大，还是110价值大就可以了，8个状态减少为7个，继续BFS下去，每一轮都合并同样状态，完成后，从最后一轮的所有状态中，找到价值最大的就ok了
由于状态最多有W+1个，进行N轮，因此复杂度O(NW)，书上说的状态迁移方程的办法其实跟这个过程很类似，不过对于有些题目，比起BFS+状态合并，状态方程的分析可以做更好的优化，如引入单调队列什么的，但BFS+状态合并可以让你得到一个没有追求极限但是也比较快的解决方案了，结合具体问题有时候更适合，比如根据问题的实际需求，搜索可以限界剪枝减少工作量，我在工作中就用过，替换了同事从wiki抄的DP算法，效率能提升一些
============我是补充的分割线====================
下午由于上班，写得比较仓促，已经有同学指出我的思路其实就是将问题转换为图中求路径，的确是这样的，这个做法虽然很多时候比教科书的状态转移方程做法稍慢，但一招就能覆盖很多问题，比如下面三道：
Problem 81 - Project EulerProblem 82 - Project EulerProblem 83 - Project Euler
这三道题都是走矩阵，要求走过的节点的值的和最小，81是只能往右和往下，一眼就是DP，82是可以上下右，可以按列DP，83是上下左右都可以，就用不上DP了，然而用单源最短路径可以通杀
因为我从开始学算法就很懒，总是追求最少的招数解决尽量多的问题，在复杂度达到了也不太会尽量追求更快，所以ACM被虐很惨，刷题请慎用，也请OJ大神们轻拍：）
可能关于“状态是怎么决定的”这个问题上面描述比较简略，就再补充一下，其实就是可能影响下一个步骤决策的因素，都是当前状态，比如上面的01背包，每次的决策是选或不选，但是如果剩余W已经不够了，就只剩下“不选”一条决策可用了，因此用剩余W来做状态
再比如这题：
Problem 191 - Project Euler抽象后其实是说：一个由L、O、A组成的长度为30的字符串，不能出现连续3个或以上的A，最多出现一个L，有多少个这样的字符串？
很明显需要30步决策，每次决策时候要从3个字母里面选合法的，O任何情况都合法，L在没出现过的情况下合法，A则在现有串最后不是AA时候合法，因此状态就是是否出现过L和最后两个字母中A的分布情况的一个组合，L是否出现有两个值，A的分布有**，A*，*A，AA四种（*代表O或L，不用展开了），所以就是2*4=8种状态啦
最后留个小题，是以前做考官时候经常用的一道面试题，印象中有算法基础的同学六七成都能立即说“用DP”，然而一问状态转移就晕了^_^：
在约定的规则下，以数字数组的形式输入一手斗地主的牌，设计算法计算这手牌最少几把可以出完
注意这里只是用斗地主做个例子，不代表牌数限制为20张，可以看做是一个N个数字根据规则分组的问题，说斗地主是因为之前是做游戏行业的，而且面试时候这样说比较容易降低同学们的紧张度，同时也是一个暗示：大家都知道斗地主靠贪心法是得不到最优出牌顺序的吧，哈。。。
动态规划问题一直是大厂面试时最频繁出现的算法题，主要原因在于此类问题灵活度高，思维难度大，没有很明显的套路做法。
也正是因为这个原因，我们将持续更新此回答来尝试破解面试中所涉及的动态规划问题。本次更新是这个系列的第一篇回答，主要目的是说明动态规划是什么，动态规划问题应该如何思考？
本次回答一共分成三个部分，具体内容框架如下所示：
一、宝石挑选
问题引入
小 Q 是一个宝石爱好者。
这一天，小 Q 来到了宝石古董店，店家觉得小 Q 是个宝石行家，于是决定和小 Q 玩一个游戏。
游戏是这样的，一共有 块宝石，每块宝石在小 Q 心中都有其对应的价值。注意，由于某些宝石质量过于差劲，因此存在只有店家倒贴钱，小 Q 才愿意带走的宝石，即价值可以为负数。
小 Q 可以免费带走一个连续区间中的宝石，比如区间 或区间
中的宝石。
请问小 Q 能带走的最大价值是多少？
问题分析
首先思考最暴力的解法。
枚举所有区间，暴力累加区间中宝石的价值，最后选一个价值最大的区间。时间复杂度 。
显然有些无法接受，因此想想有没有办法优化，比如优化掉暴力累加的部分。
优化 1.0
仔细思考不难发现，我们可以枚举区间右端点，然后固定右端点，左端点不断向左移动，边移动边累加，就可以将时间复杂度优化到 。
例如我们固定右端点是 3，那么左端点就从 3 移动到 1，边移动边累加答案，就可以在移动过程中计算出区间 、
、
的答案了。因此枚举所有区间右端点，即可在
时间复杂度内找到答案。
但是 时间还是有些过高了，因此思考有没有办法继续优化呢？
优化 2.0
观察 的解法，不难发现我们用了
的时间复杂度才求出了固定某个点为区间右端点时，区间最大价值和。
例如固定了 为区间右端点后，我们通过从
到
枚举左端点，才求出了以
为区间右端点时的区间最大价值和，即
的时间复杂度。
那么继续思考，「以 为区间右端点的区间最大和」，与「以
为区间右端点的区间最大和」，这两者是否有关联呢？
为了描述方便，接下来我们用 来代替「以
为区间右端点的区间最大和」，用
来代替第
块宝石的价值。
不难发现，如果 为正数，则
一定等于
；如果
为负数，则
一定等于
。因此我们可以推导出如下转移方程：
根据上述转移方程，我们可以在 时间复杂度内求出最大的
，即将此题时间复杂度优化到
，而这个优化的过程就是「动态规划」的过程。
在上述推导过程中，一共分为两步：
1. 将整个问题划分为一个个子问题，并令 为第
个子问题的答案
2. 思考大规模的子问题如何从小规模的子问题推导而来，即如何由 推出
这两个步骤便是「动态规划」解题思路的核心所在，即确定动态规划时的「状态」与「转移方程」。
二、动态规划概述
动态规划（Dynamic Programming），因此常用 DP 指代动态规划。本块内容我们主要讲解「动态规划解题思路」与「动态规划问题类别」。
动态规划解题思路
动态规划主要分为两个核心部分，一是确定「DP 状态」，二是确定「DP 转移方程」。
DP 状态
「DP 状态」的确定主要有两大原则：
- 最优子结构
- 无后效性
最优子结构
我们仍以「宝石挑选」例题来讲解这两大原则，首先是「最优子结构」。
什么是「最优子结构」？将原有问题化分为一个个子问题，即为子结构。而对于每一个子问题，其最优值均由「更小规模的子问题的最优值」推导而来，即为最优子结构。
因此「DP 状态」设置之前，需要将原有问题划分为一个个子问题，且需要确保子问题的最优值由「更小规模子问题的最优值」推出，此时子问题的最优值即为「DP 状态」的定义。
例如在「宝石挑选」例题中，原有问题是「最大连续区间和」，子问题是「以 为右端点的连续区间和」。并且「以
为右端点的最大连续区间和」由「以
为右端点的最大连续区间和」推出，此时后者即为更小规模的子问题，因此满足「最优子结构」原则。
由此我们才定义 DP 状态 表示子问题的最优值，即「以
为右端点的最大连续区间和」。
无后效性
而对于「无后效性」，顾名思义，就是我们只关心子问题的最优值，不关心子问题的最优值是怎么得到的。
仍以「宝石挑选」例题为例，我们令 DP 状态 表示「以
为右端点的最大连续区间和」，我们只关心「以
为右端点的区间」这个子问题的最优值，并不关心这个子问题的最优值是从哪个其它子问题转移而来。
即无论 所表示区间的左端点是什么，都不会影响后续
的取值。影响
取值的只有
的数值大小。
那怎样的状态定义算「有后效性」呢？
我们对「宝石挑选」例题增加一个限制，即小 Q 只能挑选长度 的连续区间。此时若我们定义
表示「以
为右端点的长度
的最大连续区间和」，则
的取值不仅取决于
的数值，还取决于
是如何得到的。
因为如果 取得最优值时区间长度
，则
不能从
转移得到，即
的状态定义有后效性。
最后概括一下，「最优子结构」就是「DP 状态最优值由更小规模的 DP 状态最优值推出」，此处 DP 状态即为子问题。而「无后效性」就是「无论 DP 状态是如何得到的，都不会影响后续 DP 状态的取值」。
DP 转移方程
有了「DP 状态」之后，我们只需要用「分类讨论」的思想来枚举所有小状态向大状态转移的可能性即可推出「DP 转移方程」。
我们继续以「宝石挑选」问题为例。
在我们定义「DP 状态」 之后，我们考虑状态
如何从
这些更小规模的状态转移而来。
仔细思考可以发现，由于 表示的是连续区间的和，因此其取值只与
有关，与
均无关。
我们再进一步思考， 取值只有两种情况，一是向左延伸，包含
，二是不向左延伸，仅包含
，由此我们可以得到下述「DP 转移方程」：
注意， 且
。
动态规划问题类别
讲述完 DP 问题的解题思路后，我们来大致列举一下 DP 问题的类别。
DP 问题主要分为两大类，第一大类是 DP 类型，第二大类是 DP 优化方法。
其中在 DP 类型部分，面试中最常考察的就是「线性 DP」，而在优化方法部分，最常见的是「RMQ 优化」，即使用线段树或其它数据结构查询区间最小值，来优化 DP 的转移过程。
三、习题练习
接下来我们以三道习题为例，来强化一下确定「DP 状态」和「DP 转移方程」的 DP 问题求解思路。
面试题 08.01. 三步问题
题目描述
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
示例 1:
输入：n = 3
输出：4
说明: 有四种走法示例 2:
输入：n = 5
输出：13数据范围
n 范围在 [1, 1000000] 之间解题思路
DP 问题思路主要就是确定「DP 状态」与「DP 转移方程」，因此我们首先考虑「DP 状态」。
「DP 状态」的确定有两大原则，一是「最优子结构」，二是「无后效性」，简要概括就是将原问题划分为多个子问题，且「大规模子问题最优值」仅与「小规模子问题最优值」有关，与「小规模子问题最优值」是如何得到的无关。
此题需要求出爬 n 阶楼梯的总方案数，因此很容易想到子问题是爬 i 阶楼梯的总方案数。接下来再进一步验证该状态是否符合「最优子结构」与「无后效性」两大原则。
令 表示爬
阶楼梯的总方案数，原问题被划分为了多个求最优值的子问题，继续思考，不难发现小孩爬楼梯只有三种选项，一次上 1、2、3 阶，因此
的值仅由
、
、
的值决定，因此符合「最优子结构」原则。
再进一步思考， 的取值与
、
、
的数值是如何得到的无关，因此符合「无后效性」原则。
确定完「DP 状态」后，我们再来确定「DP 转移方程」。
由于小孩只有三种爬楼选项，因此 的值仅由
决定。且由于爬楼的最后一步不同，因此
的值由
累加得到，即如下所示：
注意， ，且转移时需要注意
、
、
不要越界。
C++ 代码实现
class Solution {
public:
vector<int> f;
int mod = 1000000007;
int waysToStep(int n) {
f.resize(n+1);
f[0] = 1;
for(int i = 1; i <= n; i++) {
f[i] = f[i-1];
if(i >= 2) f[i] = (f[i] + f[i-2]) % mod;
if(i >= 3) f[i] = (f[i] + f[i-3]) % mod;
}
return f[n];
}
};
64. 最小路径和
题目描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。解题思路
仍然是相同的解题思路，即依次确定「DP 状态」与「DP 转移方程」，且「DP 状态」的确定需要满足「最优子结构」与「无后效性」。
此题需要求出从左上角出发，到达坐标 的路径数字和最小值。因此不难想到，子问题就是从左上角出发，到达坐标
的路径数字和最小值。
令 表示从左上角到坐标
的路径数字和最小值，原问题即可被划分为多个求最优值的子问题，且由于每次只能向下或向右移动一步，因此
的取值由
和
的值决定，即符合「最优子结构原则」。
进一步验证，可以发现， 的取值与
和
所对应的具体路径无关，因此符合「无后效性」。
此处啰嗦一下。如果题目改为每次可以向上、下、左、右移动一步，且不能走重复的格子，则 的值虽然与
、
、
、
的值有关，但由于「不能走重复的格子」这一限制，
所对应的具体路径会影响到
的取值，即不符合「无后效性」。
确定完「DP 状态」后，继续确定「DP 转移方程」。
由于只能向下或向右移动一步，且由于其最后一步不同，因此 由
和
中的最小值转移得到，即如下所示：
注意， 表示坐标
处的数字大小，
，转移时需要注意不要越界。
C++ 代码实现
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
for(int i = 0; i < grid.size(); i++)
for(int j = 0; j < grid[0].size(); j++) {
if(i == 0 && j == 0) continue;
int tp = 1e9;
if(i > 0) tp = min(tp, grid[i-1][j]);
if(j > 0) tp = min(tp, grid[i][j-1]);
grid[i][j] += tp;
}
return grid[grid.size()-1][grid[0].size()-1];
}
};
152. 乘积最大子数组
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。解题思路
继续采用相同的解题思路，即依次确定「DP 状态」与「DP 转移方程」，且「DP 状态」的确定需要满足「最优子结构」与「无后效性」。
此题其实是「宝石挑选」问题的进阶版，即连续区间最大乘积。因此与「宝石挑选」问题的思路一致，令 f[i] 表示以 i 为右端点的连续区间最大乘积，即可将原问题划分为多个求最优值的子问题，但这个状态定义是否符合「最优子结构」原则呢？
我们可以举一个例子来进一步思考。
例如给出 ，根据上述 f[i] 的定义，我们可以得到
。不难发现
，
的值与
的值无关，即 DP 状态最优值无法由更小规模的 DP 状态最优值推出，因此不符合「最优子结构」原则。
于是问题来了，怎样的状态定义才符合「最优子结构」呢？
继续思考可以发现，上述状态定义出错的原因主要在于如果 为负数，则
只会越乘越小。因此我们需要根据
的正负值进行分类讨论：
「以
为右端点的连续区间最小乘积」*
由此可以发现，我们需要引入新的「DP 状态」。令 表示「以
为右端点的连续区间最大乘积」，
表示「以
为右端点的连续区间最小乘积」。
不难发现 、
的取值由
、
的值推导而来，且与其具体的区间大小无关，因此同时满足「最优子结构」与「无后效性」原则。
最后我们再通过「分类讨论」即可确定如下「DP 转移方程」：
if(nums[i] > 0) {
maxn[i] = max(nums[i], maxn[i - 1] * nums[i]);
minn[i] = min(nums[i], minn[i - 1] * nums[i]);
}
else {
maxn[i] = max(nums[i], minn[i - 1] * nums[i]);
minn[i] = min(nums[i], maxn[i - 1] * nums[i]);
}
总结一下，此题根据「最优子结构」原则否定了第一种状态定义。否定之后进一步观察题目性质，得到了新的「DP 状态」，并通过「分类讨论」的方式推出「DP 转移方程」，使得本题得以圆满解决。
C++ 代码实现
class Solution {
public:
vector<int> maxn, minn;
int maxProduct(vector<int>& nums) {
int n = nums.size(), ans = nums[0];
maxn.resize(n);
minn.resize(n);
maxn[0] = minn[0] = nums[0];
for (int i = 1; i < nums.size(); ++i) {
if(nums[i] > 0) {
maxn[i] = max(nums[i], maxn[i - 1] * nums[i]);
minn[i] = min(nums[i], minn[i - 1] * nums[i]);
}
else {
maxn[i] = max(nums[i], minn[i - 1] * nums[i]);
minn[i] = min(nums[i], maxn[i - 1] * nums[i]);
}
ans = max(ans, maxn[i]);
}
return ans;
}
};
总结
最后我们来总结一下 DP 问题的解题思路：
- 确定「DP 状态」
- 符合「最优子结构」原则：DP 状态最优值由更小规模的 DP 状态最优值推出
- 符合「无后效性」原则：状态的得到方式，不会影响后续其它 DP 状态取值
- 确定「DP 转移方程」
- 分类讨论，细心枚举