当前位置：首页 > news >正文

笔记（动态规划（引入）1）

news 2026/3/26 22:34:21

笔记（动态规划（引入）1）

本系列是我自己学习的笔记，与码上学C不冲突，码上学C太慢了，仅供参考

本次学习：动态规划的最长上升子序列

看题目：

最长上升子序列

时间限制：1000ms 内存限制：128MB 栈限制：128MB

题目描述

一个数的序列bi，当b1<b2<…<bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiK)，这里1≤i1 , 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入格式

输入的第一行是序列的长度N(1≤N≤1000)。
第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出格式

最长上升子序列的长度。

样例

样例 1 输入：

7
1 7 3 5 9 4 8

样例 1 输出：

复制输入

样例解析

数据规模

PS:我当时还没学DP

直接，一个，暴力枚举，枚举所有子序列的长度

不出意料爆了

老师开讲：

动态规划（Dynamic Programming，简称DP），将一个问题拆成若干个子问题，保留子问题的最优解，防止重复计算，最终落入枚举的坑，这就是枚举与DP的不同，最终把子问题的最优解推出原问题的最优解

使用动态规划的前提：

1.最优子结构

指问题的最优解肯定包含了子结构（子问题）的最优解，就好比a->c有最优解，那么a-b,b-c也是最短路

2.重复子问题

在求解时会出现重复子问题，如果用递归，会严重超时，DP通过保留子问题最优解，避免重复计算

3.无后效性

状态一旦确定，以后的状态就与前面的状态无关了

DP的题目有几个步骤：

1.定义【状态表示】

2.确定【边界条件】，初始化dp数组

（重要！）3.推导【状态转移方程】

4.确定【状态的遍历顺序】

5.计算答案

PS:一般来说，DP题都是最值，方案数问题，像LIS，背包，都是如此，一般都在最后的题目

数字金字塔

时间限制：1000ms 内存限制：128MB 栈限制：128MB

题目描述

观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。
每一步可以从当前点走到左下方的点也可以到达右下方的点。

1
3 8
8 1 0
2 7 4 4
4 5 2 6 5

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和30

输入格式

第一个行包含R(1≤ R≤1000)，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。

输出格式

单独的一行，包含那个可能得到的最大的和。

样例

样例 1 输入：

5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11

样例 1 输出：

复制输入

样例解析

数据规模

先看这题

我们先看题目：

是一个金字塔

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

可以有很多路，要找最大路径

步骤：

1.定义状态dp[i,j]：金字塔在dp[i,j]位置中产生的最大路径数字的最大和

2.边界dp[1][1]=a[1][1]

3.状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]

4.确定顺序：是从上到下，从左到右遍历的

5.输出

res=max(dp[n][1],dp[n][2],......,dp[n][n])

为什么要这样子做？因为你不确保dp[n][n]就是最优解，所以要遍历最大值

来解析一下：

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

这是金字塔

从最顶端开始7，要么就自己下面，要么就右边

看代码：

#include<bits/stdc++.h>usingnamespacestd;intn;inta[1001][1001];intdp[1001][1001];intmain(){cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){cin>>a[i][j];}}dp[1][1]=a[1][1];//边界for(inti=2;i<=n;i++){for(intj=1;j<=i;j++){dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];}}//状态转移intres=-1;for(inti=1;i<=n;i++){res=max(res,dp[n][i]);}//最值cout<<res;return0;}

DP有以下几种：

线性DP(LIS,LCS)(LIS指最长上升与最长不上升)(LCS指最长公共子序列)
背包模型（0/1，完全，分组，组合）

区间DP

计算类DP

数位DP

状态压缩DP

树形DP

看回最长上升子序列

最长上升子序列

时间限制：1000ms 内存限制：128MB 栈限制：128MB

题目描述

输入格式

输入的第一行是序列的长度N(1≤N≤1000)。
第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出格式

最长上升子序列的长度。

样例

样例 1 输入：

7
1 7 3 5 9 4 8

样例 1 输出：

复制输入

样例解析

数据规模

假设有一个序列

1 7 3 5 9 4 8

如果枚举的话，会有$2^{n}-1 $个子序列，肯定会超时

21000−12^{1000}-121000−1就会TIE

再看回题目

1 7 3 5 9 4 8

最长序列是1 3 4 8或者1 3 5 9

长度为4

有了！

定义一个dp数组，dp[n]代表从1到N的最长上升子序列

dp[1]=1

dp[2]=?

我们看，假设1 2，那么2能接在1的后面，反过来，就是1能接在2的前面

那么只需判断a[j]是否小于a[i]，但是

我们之前不是说过每个dp[i]都可能不一样，要是我不小心把更小的数给那啥了，不就完蛋了？

所以我们还要加一个判断：

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

一切思路都搞完了，再看初始化

肯定是dp[i]=1

为什么？

因为再怎么样，都可以将a[i]看成一个序列怎么说都有1个数

为什么是

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

因为既然a[j]可以接在a[i]前面，那么是不是代表以a[j]的下标结尾的最长子序列加上1接在a[i]的结尾

也就是可能是最长序列的结尾

假设

1 7 3 5 9 4 8

那么5有没有可能是结尾？是以dp[i]结尾的最长上升子序列的长度？9？8？

所以这样就可以推出来

实在不行在正着推

a[i]一定要比a[j]大才能接在以dp[j]结尾的最长上升子序列的结尾

步骤：

1.定义状态dp[i]：以a[i]结尾的最长上升子序列

2.边界：dp[i]=1（i从1->n）

3.状态转移方程：dp[i]=max(dp[i],dp[j]+1)，当a[j]<a[i]时

4.确定遍历顺序：从左到右遍历序列

5.输出答案：

res=max(dp[1],dp[2],....,dp[n-1],dp[n])

看代码

#include<bits/stdc++.h>usingnamespacestd;intn;inta[1001];intdp[1001];intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=n;i++){dp[i]=1;//边界for(intj=1;j<i;j++){if(a[j]<a[i]){dp[i]=max(dp[i],dp[j]+1);//状态转移方程}}}intres=1;for(inti=1;i<=n;i++){res=max(res,dp[i]);}cout<<res;return0;}