ACM总结——动态规划（4）问题的形式化描述nameofcsdn的博客-

动态规划的核心在于分析最优子结构，其中包含如下内容：

如何描述问题，如何描述子问题，问题的解和子问题的解之间的关系，即递推式，问题的解空间结构，如何遍历这个解空间，等等。

问题的描述形式，取决于我们所求的答案的形式和结构.

个人理解主要分三种情形：

（1）完全按照题目所求来描述

（2）基于答案分解，附加特殊规则的精确化描述

（3）自带空间压缩的降维描述

对于问题本身的描述很复杂的题目，我们的描述越精确，我们的递推式也就越简洁。

例如：

(1)完全按照题目所求来描述

例1：力扣 OJ 1143. 最长公共子序列 https://blog.csdn.net/nameofcsdn/article/details/104091938

f(a,b)表示数组A的前a个数和数组B的前b个数的最长公共子序列

（2）基于答案分解，附加特殊规则的精确化描述

什么叫基于答案分解呢？

要求前n个数的最长上升子序列，我们可以把答案分解为n种情况：

以第i个数（i从1到n）为结尾的最长上升子序列

例2：力扣 OJ 300. 最长上升子序列 https://blog.csdn.net/nameofcsdn/article/details/104086350

给定一个无序的整数数组，找到其中最长上升子序列的长度。

f(i)表示以第i个数结尾的最长上升子序列的长度

f(i-1)表示以第i-1个数结尾的最长上升子序列的长度

所以f(i)=max{f(j) | j<i && num[j]<num[i]}

例3：CSU 1225: ACM小组的队列（最长上升子序列的个数）https://blog.csdn.net/nameofcsdn/article/details/79747086

这个题目需要把以第i个数结尾的最长上升子序列的长度和数目一起算出来。

PS：完全按照题目所求来描述，求得的值就是答案，

基于答案分解，附加特殊规则的精确化描述，求得值之后，还要在所有值里面取一个最优解

PS：基于答案分解是根据答案的最后一个值，分解成很多情况，得到的是分解问题，形式和原问题不同

而子问题是形式和原问题相同，但规模比原问题小，是原问题经过分治思想得到的。

（3）自带空间压缩的降维描述

首先，什么是空间压缩？

ACM总结——动态规划（3）空间压缩 https://blog.csdn.net/nameofcsdn/article/details/106507259

再看看什么叫自带空间压缩的降维描述：

例4：力扣OJ 1218. 最长定差子序列 https://blog.csdn.net/nameofcsdn/article/details/106418150

给定差值dif，求最长等差子序列

如果数组没有重复的数，那就简单，ans[arr[i]]=ans[arr[i]-dif]+1

如果有重复的数，那么相同的数如何选取？

自然是取第i个数之前，等于arr[i]-dif且ans值最大的那个，但是如果搜索的话就会超时，必须在O（1）的时间内找到这个数或者找到它的ans值。

所以我们除了需要知道ans[arr[i]]表示以第i个数结尾的最长等差子序列之外，还需要确定，ans[x]表示啥？

ans[x]=ans[arr[j]]，其中j=max{j | arr[j]=x，j<i}

没错，这么一个精准的形式化描述，让我们意识到，ans[x]的含义中包含了i这个变量，也就是说ans数组的值的含义是随着时间一直在变化的，这其实是隐含了空间压缩。