动态规划DP整理

动态规划DP整理

1.什么是动态规划

动���规划是常用的算法，主要用于解决需要多个步骤或者多方面考虑的问题，如以下三个常见问题：

1.重叠子问题

重叠子问题是指在一个大问题中，我解决该大问题分为多个小问题，这些多个小问题之间又没有必然的联系，比如数组的划分问题，前一组的划分对后一组有定的影响，但是却没有必然的联系，因为划分有多种方式，这时候就可以用DP来解决问题，把每个小划分看成独立的问题。

2.最优子结构问题

最优子结构问题就是在众多方案这种找到一个最优解，最具代表性的就是打劫问题，如一个土匪要有20个目标可以打劫，但是因为时间问题，最多只能打劫10家，这时候就要用DP来算出最优方案。

3.无后效性问题

无后效性又称为马尔可夫性（Markov property），是一个概率论中的概念。无后效性是指如果给定某一阶段的状态，则此阶段以后过程的发展仅与此阶段的状态有关，而不受此阶段以前各阶段状态的影响。通常浓缩成一句简短的“未来与过去无关”。问题的历史状态不影响未来的发展，只能通过当前的状态去影响未来，当前的状态是以往历史的一个总结。在利用动态规划方法求解多阶段决策问题时，过程的状态必须具有无后效性。具体地说，如果k阶段的值已经确定，则在k+1阶段只关心k阶段的值，而不用关心k阶段的值是怎么求出来的，也不用关心k阶段以前的阶段的值。

2.动态规划的本质

1.状态描述和初始状态

动态规划按照数学的理论和物理理论来说，就是将问题的某个节点从时空中抽象出来，把由多个状态和事件组成的问题，一帧一帧的抽象成一个时间节点，而这个时间节点则是由其状态和状态转移方程组成。

下一个定义的话就是，一个问题在某个时空节点的状态以及其对下一个时间节点的影响或者受到来自上一个时间节点的影响，称为状态描述。我们把第一个独立出来的时空节点称为初始状态。

2.状态转移

状态转移是指在某个状态下，该状态对下一个状态产生的影响传递。简单来说，就是该状态会把自己对下一个状态产生的影响传递给下一个状态，而受到影响的下一个节点则会接收这个影响，这个传递和接收的过程叫做状态转移。对状态转移进行数理化描述的公式叫做状态转移方程。

3.动态规划的解题步骤

1.定义问题的状态

定义问题的状态是要明确状态表示什么含义，定义的状态需要满足最优子结构和无后效性，如果问题的状态定义得不对，会导致无法用动态规划来求解。

具体到代码中，就是要定义 dp 数组中每个元素的含义，以及 dp 数组中下标的含义。代码中一般都会用一个数组来存储所有子问题状态的值，这个数组可以是一维数组 dp[i] 或二维数组 dp[i][j] 等。明确状态的含义是列出状态转移方程和问题求解的前提。

2.列出状态转移方程

状态转移方程是指从前序状态推导出当前状态的推导关系，通常可以用问题规模的多项式来表示，所以也常称为递推公式。列出正确的状态转移方程，是动态规划问题中非常重要的一个步骤，也是一个比较困难的步骤。

具体到代码中，就是找到 dp[i] 与 dp[i-1]，dp[i-2], … 的关系，用 dp[i-1]，dp[i-2], … 来表示 dp[i] 。例如，用 dp[i] 表示 i 的阶乘，则 dp[i] = i * dp[i-1]，用 dp[i] 表示斐波那契数列，则 dp[i] = dp[i-1] + dp[i-2] 。递推公式在不同问题中是千变万化的，所以要分析清楚问题，从定义状态时就开始考虑递推公式的推导，假如无法得到递推公式，可以重新分析问题的状态定义得是否适合。

3.状态初始化

在定义完状态和找到递推公式后，需要求解问题的初始值，才能有递推解决问题的起点。动态规划的每一个状态都是从前序状态推导而来的，所以一定有初始值，也就是状态转移的起点。不过，起始状态并不是一成不变的，要根据定义的状态，找到有意义的初始值。

具体到代码中，求初始值就是求出起始状态的值。例如，阶乘的初始值是 dp[1] = 1，斐波那契数列的初始值是 dp[1] = 1, dp[2] = 1。在具体问题中，有些问题的初始值是从下标 1 开始，有些问题的初始值是从下标 0 开始，还有些问题的初始值是从 n-1 开始，等等。有些问题需要一个初始值，有些问题需要多个初始值。所以在求初始值时要根据状态定义和递推公式来调整，具体问题具体分析。

4.代码求解

前面的三个步骤主要是对问题进行剖析，找到解决问题的方法。

完成前面的步骤后，我们需要根据思路编写代码、运行代码得到结果。相对于前面三步而言，编写代码其实是最简单的一步，动态规划的代码通常像套公式一样，因为只要经过了前面的分析，写代码只是把结果计算出来。虽然说，不编写代码并执行，就得不到结果，但是在动态规划中，关键在于解题思路，很多人甚至没有把编写代码当成一个步骤

4.动态规划实例

问题来源：l在这里插入图片描述

eetcode 2369题（讲解） 以及 leetcode 198题(练习)

讲述来源以及根据：灵茶山艾府

class Solution {public:    bool validPartition(vector& nums)     {        int length=nums.size();        vector f(length+1,0);        f[0]=true;        for(int i=1;i1&&f[i-2]&&(nums[i]==nums[i-1]&&nums[i]==nums[i-2]||nums[i]==nums[i-1]+1&&nums[i]==nums[i-2]+2))            {                f[i+1]=true;            }        }        return f[length];    }};