长沙网站建设营销,友链网,质量最好的购物平台,WordPress中文替换布前言
在说线性dp之前#xff0c;我们先来聊一聊动态规划是啥#xff1f;
动态规划到底是啥#xff1f;
动态规划是普及组内容中最难的一个部分#xff0c;也是每年几乎必考的内容。它对思维的要求极高#xff0c;它和图论、数据结构不同的地方在于它没有一个标准的数学…前言
在说线性dp之前我们先来聊一聊动态规划是啥
动态规划到底是啥
动态规划是普及组内容中最难的一个部分也是每年几乎必考的内容。它对思维的要求极高它和图论、数据结构不同的地方在于它没有一个标准的数学表达式和明确清晰的解题方法。
动态规划是对求解最优解的一种途径而不是一种特殊的算法。由于各种问题的性质不同确定最优解的条件也互不相同因而动态规划的设计方法对不同的问题有各具特色的阶梯方法而不存在一种万能的动态规划算法。为了方便学习我们把若干具有代表性的动态规划问题归纳总结成不同的几类并建立对应的数学模型。
动态规划一般用来求解多阶段决策问题的最优解可以将过程分成若干个互相联系的阶段在它的每一阶段都需要做决策从而使整个过程达到最好的活动效果。各个阶段决策的选取不是任意确定的它依赖于当前面临的状态又影响以后的发展当各个阶段决策确定后就组成一个决策序列因而也就确定了整个过程的一条活动路线。 对于动态规划问题最重要的是分析出 一、决策对象我们需要对题目中的哪个变量进行决策。 二、阶段需要将问题的全过程恰当的分成若干个相互联系的阶段以便按一定的次序去求解。阶段的划分一般是根据时间(先后顺序) 和 空间(大小关系) 的自然特征来划分。 三、状态某一阶段的出发位置称为状态一个阶段可能包含多个状态状态大多都是用 数组 来表示即表示我们需要的答案。 四、决策分析完问题后我们应该怎么解决问题。 五、状态转移方程描述前一阶段到后一阶段的状态演变规律。
线性动态规划
线性动态规划是动态规划中比较简单的一类问题他的状态转移是线性的即状态的转移是固定的常见的如从前到后或者从后到前。线性动态规划和递推比较类似在很多情况下这两种做法大致是相同的。一般的递推是当前要求解的答案和前面某个固定答案有关而线性动态规划是当前答案和前面的某个答案存在关系这个位置在不同的情况下是不相同的。
最长上升子序列
言归正传我们继续聊线性dp。
子集和子序列和子串的区别
以 a b f s g e g s a s abfsgegsas abfsgegsas为例 f a g g a s faggas faggas是它的子集因为子集是不计顺序的 a b g g s s abggss abggss 则是他的子序列因为子序列是要求有顺序的而 a b f abf abf则是他的字串
内容分析
决策对象 每个位置上的数。
阶段 共有 n n n 个数因此有 n n n 个阶段。
状态 因为每个数都有可能是子序列的结尾所以使用 dp[i] 表示以第 i i i 个数作为结尾的最长上升子序列的长度。
决策 如果以第 i i i 个数作为结尾那么在这个序列中上一个数一定要小于 a [ i ] a[i] a[i]。因此我们需要在前面的数中找到比 a [ i ] a[i] a[i] 小的数而且我们应该选择以这个数结尾的最长上升子序列中最长的那个这样接在这个数后面得到的序列也是最长的。
状态转移方程 如果 h [ k ] h [ i ] h[k]h[i] h[k]h[i]则 d p [ i ] m a x ( d p [ i ] , d p [ k ] 1 ) dp[i]max(dp[i],dp[k]1) dp[i]max(dp[i],dp[k]1)其中 k ∈ [ 1 , i − 1 ] k\in[1,i-1] k∈[1,i−1]。
最后我们找到最大的 d p [ i ] dp[i] dp[i] 就是答案。
#includebits/stdc.h
using namespace std;int a[10010],dp[10010],ansINT_MIN;
int main(){int n;cinn;for (int i1;in;i){cina[i];dp[i]1;} for (int i1;in;i){for (int j1;ji;j){if (a[j]a[i]){dp[i]max(dp[i],dp[j]1);}}ansmax(ans,dp[i]);}coutans;return 0;
}
