动态规划第一节课

都讲了这么多图论了，我们要不学学动态规划吧(为了应付考试)

文章目录

• 动态规划第一节课
• • 1.1 最长递增子序列

1.1 最长递增子序列

子串和子序列的区别

子串：一段连续的空间

子序列：抠掉一些数

最长上升子序列

令 d p i dp_i dpi​ 是以i结尾的最长上升子序列的长度

比如说fib数列

f i = f i − 1 + f i − 2 f_i = f_{i-1} + f_{i-2} fi​=fi−1​+fi−2​

但最长上升子序列呢？

我们先来模拟一下序列 1   4   2   5   3   6 1\space4\space2\space5\space3\space6 1 4 2 5 3 6

d p 1 = 1 dp_1=1 dp1​=1

d p 2 = 2 dp_2=2 dp2​=2

d p 3 = d p 1 + 1 = 2 dp_3=dp_1+1=2 dp3​=dp1​+1=2

在 d p 4 dp_4 dp4​中：我们可以让 1 1 1， 4 4 4， 2 2 2中的任意一个值来加，所以for一遍枚举   1 → i − 1   ~1\to i-1~  1→i−1 求最大值即可。

继续往后推：

d p 4 = 3 dp_4=3 dp4​=3

d p 5 = 3 dp_5=3 dp5​=3

d p 6 = 4 dp_6=4 dp6​=4

好了，就这么简单！

代码

#include <iostream>
#include <cstdio>
using namespace std;

int a[10010];
int dp[10010];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i ++)
    {
        dp[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[i] > a[j])
        {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int mx = 1;
    for(int i = 2; i <= n; i ++)
    {
        mx = max(mx, dp[i]);
    }
    printf("%d\n", mx);
    return 0;
}