GESP6级C++考试语法知识（四十二、动态规划----线性DP（三、最长上升子序列（LSI）启蒙））

第二阶段第三课

🚂《最长上升火车——LIS启蒙》

🌟一、故事开始：火车总站比赛

1、在算法王国里，

有一个巨大的火车总站。

2、今天，

国王举办了一场特别比赛：

🚂最长上升火车序列大赛

3、规则非常奇怪：

每节车厢上，

都写着一个数字。

例如：

3 1 2 5 4 6

国王说：

4、🌟你可以选择一些车厢连接起来

但是：

必须保持原来的先后顺序！

而且：

后面的数字必须越来越大！

5、例如：

1 2 5 6

可以。

因为：

1 < 2 < 5 < 6

6、但是：

3 2 5

不行。

因为：

3 > 2

下降了！

7、国王的问题来了：

🌟最长能组成多长的上升火车？

🌟二、什么叫上升序列？

1、例如：

1 2 3

是上升。

2 5 8 10

也是上升。

因为：

后面都比前面大。

2、而：

5 3 7

不是。

因为：

5 > 3

下降了。

🌟三、题目例子

1、车厢数字：

3 1 2 5 4 6

（1）可以选：

1 2 5 6

长度：

4

（2）也可以选：

1 2 4 6

长度：

4

2、答案：

4

🌟四、动态规划登场

1、以前：dp[i]表示：

方案数

或者最大价值。

2、今天：

我们重新定义！

🌟状态定义

dp[i]

表示：

以第 i 个车厢结尾的最长上升子序列长度

3、注意：

是：

以 i 结尾！

这句话非常重要！

🌟五、为什么这样定义？

1、例如：

3 1 2 5 4 6

2、看数字：

5

3、我们问：

以5结尾的最长上升序列多长？

4、我们真正需要考虑的是，5与前面的谁，可以相连

3 1 2 5 4 6 dp[0] = 0 // 还没车厢 dp[1] = 1 // 就一个车厢 3 dp[2] = ? // 有2 种可能性， //第一种可能性，它就自己组成数列为1 dp[2] = 1 //第二种可能性，它加在DP[1]的后面，3 > 1显然加不上 //取最大值： dp[2] = 1 dp[3] = ? //有3种可能性 //第一种可能性，它就自己组成数列为1 dp[3] = 1 //第二种可能性，它加在DP[1]的后面，3 > 2显然加不上 //第三种可能性，它加在DP[2]的后面，1 < 2显然可以加 dp[3] = 1+1=2 //取最大值： dp[3] = 2 dp[4] = ? //有4种可能性 //第一种可能性，它就自己组成数列为1 //第二种可能性，它加在DP[1]的后面，3 < 5显然可以加 dp[4] = 1 +1 =2 //第三种可能性，它加在DP[2]的后面，1 > 5显然可以加 dp[4] = 1 +1 =2 //第四种可能性，它加在DP[3]的后面，2 < 5显然可以加 dp[4] = 2 +1 =3 //取最大值： dp[4] = 3

5、最终答案：

1 2 5

长度：

3

5、所以：

dp[4]=3

🌟六、状态转移

1、现在来到第 i 个数字。

（1）例如：

a[i]=5

（2）它前面有很多数字：

3 1 2

（3）如果：

2 < 5

那么：

5就能接在2后面！

（4）于是：

1 2

后面接：

5

得到：

1 2 5

长度增加1。

（5）所以只要：

a[j] < a[i]

那么：

dp[i] = dp[j]+1

算完还是要打擂台,求max。

（6）🌟状态转移公式

dp[i]= max(dp[i],dp[j]+1)

条件：

a[j] < a[i]

🌟七、不要忘记初始化

每个数字自己都能组成：

自己

这个序列。

例如：

5

长度：

1

所以：

dp[i]=1;

🌟八、填写DP表

1、数组：

3 1 2 5 4 6

2、开始：

3、最终：

最大值：

4

答案：

4

🌟九、参考代码

#include <iostream> using namespace std; int a[1005]; int dp[1005]; int main() { int n; cin >> n; for(int i=1;i<=n;i++) { cin >> a[i]; } int ans = 0; for(int i=1;i<=n;i++) { dp[i] = 1; for(int j=1;j<i;j++) { if(a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } cout << ans; return 0; }

🌟十、为什么LIS还是线性DP？

1、因为状态仍然是一维：

dp[1] dp[2] dp[3] ... dp[n]

2、虽然：

每个状态要回头看前面很多状态。

3、但本质仍然是：

🌟一维状态转移

4、所以：

它依然属于：

⚔️线性DP⚔️

🌟十一、课堂挑战

🎯挑战1

同学们来填DP表：

1 5 2 3 4 6

🎯挑战2

同学们来计算：

5 4 3 2 1

答案是多少？

🎯挑战3

如果要求：

最长下降子序列

怎么办？

提示：

把：

a[j] < a[i]

改成：

a[j] > a[i]

🌟十二、举一反三

LIS是竞赛里的超级经典模型。

以后很多题都会变形：

🚀合唱队形

🚀友好城市

🚀最长不下降序列

🚀最长下降序列

这些题目本质都是：

🌟LIS模型

🌟十三、本课总结

✅ dp[i]

表示：

以第 i 个数字结尾的最长上升子序列长度

✅ 初始化

dp[i]=1;

✅ 转移条件

a[j] < a[i]

✅ 转移公式

dp[i] = max(dp[i], dp[j] + 1)

✅ 最终答案

所有 dp[i] 中的最大值

🌟下节课预告

下一课：

🎵《动物王国合唱团——LIS + LDS 联手出击》

让同学们理解与掌握

数学种的：

🌟双调序列

(Bi-tonic Sequence)