什么是动态规划
用于求解某种最优性质的问题。
将带求解问题分解为若干个子问题，解决子问题，然后从这些子问题的解得到原问题的解
两个要素：状态和转移。
阶段 ：求解的问题的每个过程。
状态 ：状态表示每个阶段所处的情况。
策略 ：策略是按顺序排列的策略组成的集合。 状态转移方程 ；状态转移方程是确定过程由一个状态到另一个状态的过程。
什么时候使用动态规划
最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，那么该问题具有最优子结构性质。（LIS）
子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。（求Fibonacci）
无后效性：对于某个阶段状态，只能由前面的状态转移到，且不可以转移到前面。（对于有负边权求最短路，dijkstra是不可做的）\
动态规划是干什么的
DP常常适用于有重叠子问题和最优子结构性质的问题。
这时候就有许多同学，就开始问了：那他的步骤呢
很简单
设状态 列转移方程
今年普及组的同学注意了
常见动态规划类型有
背包问题
LIS
LCS
括号序列计数
区间DP
树形DP
数位DP
状压DP
概率期望DP
那我们就开始今天的练习
爬楼梯问题
一个人每次只能走1层楼梯或者2层楼梯，问走到第n层楼梯一共有多少种方法。
n<=1000000数楼梯 - 洛谷https://www.luogu.com.cn/problem/P1255Fibonacci。
设状态：f[i]表示走到第i层的方案数。
列转移方程：
f[i] = f[i-1]+f[i-2]边界条件：
f[0] = 1, f[1] = 1;记忆化搜索
复杂度分析（评价一个动态规划算法设计的好坏）：
空间复杂度：
转移复杂度：
总复杂度：
疯狂的爬楼梯问题
一个人每次只能走2层楼梯，22层楼梯，222层楼梯，问走到第n层楼梯一共有多少种方法。
n<=1000000那这到题该怎么做呢
设状态：f[i]表示走到第i层的方案数。
列转移方程：
f[i] = f[i-2] + f[i-22] + f[i-222]边界条件：
f[0] = 1 f[1] = 1复杂度分析（评价一个动态规划算法设计的好坏）：
空间复杂度：
转移复杂度：
总复杂度：
超级疯狂的爬楼梯问题
一个人每次最少走1层楼梯，最多t层楼梯。
问走到第n层楼梯一共有多少种方法。
n<=1000000其中有许多层楼梯上会有石头，求最少经过多少石头到达n层。 比如第1层有2个石头，第2层有10个石头，第3层有2个石头，每次最多走两层。
那么显然0-1-3只需要经过4个石头
n<=1000000
设状态：f[i]表示到第i层最少经过多少石头。
列转移方程 如果i处没有有石头
f[i] = min(f[i – 1], f[i – 2] … f[i-k])如果i处有石头
f[i] = min(f[i-k]) + a[i]（a[i]为第i层的石头）
复杂度：
空间：
转移：
总复杂度：
LIS 最长上升子序列
给出一个序列，求出最长的不下降子序列的长度
n<=10002,7,3,4,8,5 2,3,4,5
answer = 42533 -- Longest Ordered Subsequencehttp://poj.org/problem?id=2533[NOIP2004 提高组] 合唱队形 - 洛谷https://www.luogu.com.cn/problem/P1091
LIS 解法
设状态：f[i]表示到第i个位置的最长上升子序列。
列转移方程：
f[i] = max(f[j])+1, j<=i且h[i]>h[j]复杂度：
空间：
转移：
总复杂度：文章来源：https://www.toymoban.com/news/detail-472885.html
LIS nlogn解法
g[i]表示所有长度为i的最长上升子序列中，末尾元素最小的是多少。
g[i]是递增的。 那么对于第i个数x，在g数组中找到第一个小于它的数就好了。
即g[j]<=x的最大的j（也就是x能够正好插入的位置） 令g[j+1]=min(g[j+1],x);
二分查找优化，复杂度为
LIS 合唱队形
[NOIP2004 提高组] 合唱队形 - 洛谷https://www.luogu.com.cn/problem/P1091文章来源地址https://www.toymoban.com/news/detail-472885.html
求一遍最长上升子序列和最长下降子序列，扫一遍统计答案。
到了这里，关于动态规划（DP）C++讲解，看着这一本就够了的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
