。

它对思维的要求极高#xff0c;它和图论、数据结构不同的地方在于它没有一个标准的数学…前言

动态规划是普及组内容中最难的一个部分也是每年几乎必考的内容。

它对思维的要求极高它和图论、数据结构不同的地方在于它没有一个标准的数学表达式和明确清晰的解题方法。

动态规划是对求解最优解的一种途径而不是一种特殊的算法。

由于各种问题的性质不同确定最优解的条件也互不相同因而动态规划的设计方法对不同的问题有各具特色的阶梯方法而不存在一种万能的动态规划算法。

为了方便学习我们把若干具有代表性的动态规划问题归纳总结成不同的几类并建立对应的数学模型。

动态规划一般用来求解多阶段决策问题的最优解可以将过程分成若干个互相联系的阶段在它的每一阶段都需要做决策从而使整个过程达到最好的活动效果。

各个阶段决策的选取不是任意确定的它依赖于当前面临的状态又影响以后的发展当各个阶段决策确定后就组成一个决策序列因而也就确定了整个过程的一条活动路线。

二、阶段需要将问题的全过程恰当的分成若干个相互联系的阶段以便按一定的次序去求解。

阶段的划分一般是根据时间(先后顺序)

空间(大小关系)

三、状态某一阶段的出发位置称为状态一个阶段可能包含多个状态状态大多都是用

线性动态规划

线性动态规划是动态规划中比较简单的一类问题他的状态转移是线性的即状态的转移是固定的常见的如从前到后或者从后到前。

线性动态规划和递推比较类似在很多情况下这两种做法大致是相同的。

一般的递推是当前要求解的答案和前面某个固定答案有关而线性动态规划是当前答案和前面的某个答案存在关系这个位置在不同的情况下是不相同的。

最长上升子序列

小的数而且我们应该选择以这个数结尾的最长上升子序列中最长的那个这样接在这个数后面得到的序列也是最长的。

状态转移方程

(a[j]a[i]){dp[i]max(dp[i],dp[j]1);}}ansmax(ans,dp[i]);}coutans;return