3 条题解

  • 2

    哈喽小朋友们,我是你们的 FARO 学长,今天我来带你们刷这道经典的动态规划题
    动态规划的思路,是要将大问题分割成重复子问题,然后列出状态转移方程求解
    这道题的状态转移方程十分明了,dp[i]=max(dp[k])+1,其中 dp[k] 表示 0~i-1 中所有 list[k]<list[i] 的情况

    什么,你说你看不懂 java?那快去学啊

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    public class Main {
        private static final Scanner sc = new Scanner(System.in);
        public static void main(String[] args) {
            int n = sc.nextInt();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(sc.nextInt());
            }
            System.out.println(getMaxUpSeq(list));
        }
    
        public static int getMaxUpSeq(List<Integer>list) {
            // 状态转移方程:dp[i]=max(dp[k])+1 dp[k] 表示 0~i-1 中所有 list[k]<list[i] 的情况
            if (list.size()==0) return 0;
            int res = 1;
            int[] dp = new int[list.size()];
            dp[0]=1;
            for (int i = 1; i < list.size(); i++) {
                int currMax=0;
                for (int j = 0; j < i; j++) {
                    // 找到 dp[k]
                    if (list.get(j)<list.get(i)) currMax=Math.max(currMax,dp[j]);
                }
                dp[i]=currMax+1;
                res = Math.max(res,dp[i]);
            }
            return res;
        }
    }
    
    

    同学们可以关注一波我的公众号:程序员FAROZ
    微信公众号 二维码
    随时获得更多学习资讯哦

    pic1

  • 2

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

    int main()
    {
    int a[100001],top=0,n,x;
    cin>>n>>x;
    a[++top]=x;
    for(int i=2;i<=n;++i)
    {
    cin>>x;
    if(x>=a[top])
    a[++top]=x;
    else
    {
    int p=upper_bound(a+1,a+top+1,x)-a;
    a[p]=x;
    }
    }
    cout<<top;
    }

  • -3
    @ 2019-02-07 21:14:17

    #include <stdio.h>
    #include <algorithm>
    #define MAX_N 20000
    using namespace std;
    int n;
    int a[MAX_N];
    int dp[MAX_N];
    void solve();
    int main()
    {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    scanf("%d", &a[i]);
    solve();
    return 0;
    }
    void solve()
    {
    int res = 0;
    for (int i = 0;i < n; i++)
    {
    dp[i] = 1;
    for (int j = 0; j < i; j++)
    if (a[j] < a[i])
    {
    dp[i] = max(dp[i], dp[j] + 1);
    }
    res = max(res, dp[i]);
    }
    printf("%d\n", res);
    }

  • 1

信息

难度
7
分类
(无)
标签
递交数
490
已通过
112
通过率
23%
被复制
7
上传者