首页 > 其他分享 >线性DP

线性DP

时间:2024-06-17 11:33:44浏览次数:11  
标签:String nums int 数组 线性 new public DP

LeetCode 300. 最长递增子序列

LeetCode674. 最长连续递增序列

题解:最长上升子串模板题

定义fi表示以i结尾的最长上升子串

nums[i-1] < nums[i],则有f[i] = f[i-1] + 1
nums[i-1] > nums[i],则有f[i] = 1

public class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        int res = 1;
        for(int i = 0; i < n; i++) {
            if(i > 0 && nums[i] > nums[i-1]) f[i] = f[i-1] + 1;
            res = Math.max(res, f[i]);
        }
        return res;
    }
}

携程2023030701

题目内容

定义一个数组为“稳定的”,当且仅当数组中相邻的两个元素之差的绝对值不超过1。

例如:

  • 数组 [2, 3, 2, 2, 1] 是稳定的,因为相邻元素之差不超过1。
  • 数组 [1, 3, 2] 不是稳定的,因为1和3之间的差的绝对值超过了1。

给定一个由 n 个整数组成的数组 a,求该数组的最长的稳定的连续子数组的长度。

输入描述

第一行输入一个正整数 n,代表数组的大小。

第二行输入 n 个正整数 ai,代表数组的元素。

1 ≤ n ≤ 100000,1 ≤ ai ≤ 10^9

输出描述

一个正整数,代表最长连续稳定子数组的长度。

样例

输入

6
2 3 5 4 5 6

输出

4

思路

likou674. 最长连续递增序列差不多。
f[i] 为以 i 结尾的稳定子数组的长度。

f[i] 初始值为 1,如果它与它左侧的元素 nums[i-1] 的差值 diff = abs(nums[i] - nums[i-1]) 满足 diff ≤ 1,则有 f[i] = f[i-1] + 1

`import java.util.*;

public class Main {
static final int N = 100010;
static int n, a[] = new int[N], f[] = new int[N];

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    for (int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
    }
    int res = 1;
    f[0] = 1;
    for (int i = 1; i < n; i++) {
        if (Math.abs(a[i] - a[i - 1]) <= 1) {
            f[i] = f[i - 1] + 1;
        } else {
            f[i] = 1;
        }
        res = Math.max(res, f[i]);
    }
    System.out.println(res);
}

}`

科大讯飞2022101001

输入:

第一行字符串表示赛道X的奖金编号。
第二行字符串表示赛道Y的奖金编号。
编号范围为a-z和0-9,赛道关卡数为1-100。

输出:

两兄弟最多可获得的奖金数。

示例:

输入:

1323467
1378694

输出:

4

说明:
如赛道X和Y中获得奖金1和6,不连续,获得2份奖金;
如获得奖金1和3,连续,获得4份奖金。

思路:
这道题和力扣718.最长连续子数组一模一样

定义 f[i][j] 为以 nums1[i] 结尾和以 nums2[j] 结尾的最长公共子串

  • nums1[i] 不等于 nums2[j],则有 f[i][j] = 0
  • nums1[i] 等于 nums2[j],则有 f[i][j] = f[i-1][j-1] + 1
package com.coedes.dp.kedaxunfei20221010;

import java.util.Scanner;

/**
 * @author 17259
 * @create 2024-06-15 17:51
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String X = sc.nextLine();
        String Y = sc.nextLine();
        System.out.println(solve(X, Y));
    }

    private static int solve(String X, String Y) {
        int lenX = X.length();
        int lenY = Y.length();
        int[][] dp = new int[lenX + 1][lenY + 1];
        int res = 0;
        for (int i = 1; i <= lenX; i++) {
            for (int j = 1; j <= lenY; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } 
                res = Math.max(dp[i][j],res);
            }
        }
        return res*2;
    }
}

20221013荣耀

在某个遥远国度里有一种传统的游戏叫做“跳跳棋”。游戏棋盘呈直线状,共有N格,起始位置和结束位置在棋盘之外。每格有不同的积分值,玩家每次跳跃必须跳过一个或多个格子,不允许跳到相邻格子或回跳。目标是通过跳跃获取最高积分。

输入描述:

  • 第一行是整数N,表示跳棋格数(1 ≤ N ≤ 100,000)
  • 第二行是N个整数,每个整数表示对应格子的积分值(1 ≤ M ≤ 1,000)

输出描述:

  • 能获得的最高积分

示例:
输入

3
1 5 2

输出

5

思路:
这和力扣198.打家劫舍 思路一样,
起始位置和结束位置在棋盘之外 且 (1 ≤ N ≤ 100,000) ,定义长度为 N+1 数组 ,起点为0

package com.coedes.dp.rongyao20221013;

import java.util.Scanner;

/**
 * @author 17259
 * @create 2024-06-16 10:44
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N  = sc.nextInt();
        int[] M = new int[N+1];
        for (int i = 1; i <= N; i++) {
            M[i] = sc.nextInt();
        }
        System.out.println(solve(M));
    }

    private static long solve(int[] m) {
        int length = m.length;
        long[] dp = new long[length];
        dp[1] = m[1];
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+m[i]);
        }
        return dp[length-1];
    }
}

2023081101 快手

一个整数数组中选出一些数,使得这些数的和尽可能大,但不允许选择相邻的元素。要求设计一个算法,在O(n)的时间复杂度内计算出答案。

输入描述:

  • 一行输入包含n个正整数,以EOF结尾。

输出描述:

  • 第一行输出选中的数在整数数组中的索引,空格隔开,以空格结束。
  • 第二行输出选中的数的和。

示例:
输入

1 6 2 7 3 8 4 9 5 10

输出

1 3 5 7 9 
40

思路:
打家劫舍 + 标记数组

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * @author 17259
 * @create 2024-06-16 12:51
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int n = split.length;
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(split[i - 1]);
        }
        solve(a, n);
    }

    private static void solve(long[] a, int n) {
        long[] dp = new long[n + 1];
        boolean[] flag = new boolean[n + 1];
        dp[0] = 0;
        dp[1] = a[1];
        flag[1] = true;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1];
            long val = dp[i - 2] + a[i];
            if (val > dp[i]) {
                dp[i] = val;
                flag[i] = true;
            }
        }
        List<Integer> ans = new ArrayList<>();
        int cur = n;
        while (cur > 0) {
            if (flag[cur]) {
                ans.add(cur - 1);
                cur -= 2;
            } else {
                cur -= 1;
            }
        }
        for (int i = ans.size() - 1; i >= 0; --i) {
            System.out.print(ans.get(i) + " ");
        }
        System.out.println();
        System.out.println(dp[n]);
    }
}

标签:String,nums,int,数组,线性,new,public,DP
From: https://www.cnblogs.com/alohablogs/p/18232410

相关文章

  • 基于Matlab的LDPC编解码算法实现的及LDPC码性能测试+源代码+文档说明
    文章目录源码下载地址@[toc]源码下载地址项目介绍项目功能界面预览项目备注源码下载地址项目介绍项目功能界面预览项目备注源码下载地址源码下载地址@[toc]源码下载地址点击这里下载代码项目介绍LDPC码背景及概要LDPC是LowDensityParityCheckCode英文缩写,意......
  • 消灭事件回调,让其直接变成线性同步的代码风格
    在C#和Javascript语言下,讨论如何封装事件返回的回调问题场景比如有一个库中,有一个send方法,用于发送命令,然后需要等待返回值,但send方法本身没有返回值,而是通过另外的事件来获取返回值。伪代码如下://通过事件回调来接收命令执行结果foo.onDataReceive=(result)=>{......
  • 08_线性回归详解
    线性回归详解1、包导入与数据创建importnumpyasnpimportmatplotlibimportmatplotlib.pyplotasplt#绘图全局参数设置config={"font.family":'TimesNewRoman',"font.size":14,"font.serif":'Simsun',}matplo......
  • Tektronix 泰克DPO7254C 数字荧光示波器
    Tektronix泰克DPO7254C数字荧光示波器DPO7054C(500MHz)DPO7104C(1GHz)DPO7254C(2.5GHz)DPO7354C(3.5GHz)主要性能指标3.5 GHz、2.5 GHz、1 GHz和500 MHz带宽型号在一条通道上提供了高达40 GS/s的实时采样率,在两条通道上提供了20GS/s的实时采样率,在三或四条通道......
  • Tektronix 泰克 DPO7354C 数字示波器
    Tektronix泰克DPO7354C数字示波器DPO7054C(500MHz)DPO7104C(1GHz)DPO7254C(2.5GHz)DPO7354C(3.5GHz)主要性能指标3.5 GHz、2.5 GHz、1 GHz和500 MHz带宽型号在一条通道上提供了高达40 GS/s的实时采样率,在两条通道上提供了20GS/s的实时采样率,在三或四条通道上提......
  • 解锁Java高效并发:newFixedThreadPool深度剖析与实战
    1.引言在Java的并发编程中,线程池是一个重要的概念。而newFixedThreadPool作为Java标准库java.util.concurrent中Executors类的一个静态方法,为开发者提供了一个固定大小的线程池实现。本文旨在深入剖析newFixedThreadPool的原理、源码实现以及最佳实践,更好地理解和应用它。......
  • 第七章 线性判别分析LDA(7.1)
    一、基本代码:sklearn.discriminant_analysis.LinearDiscriminantAnalysis(solver='svd',shrinkage=None,priors=None,n_components=None,store_covariance=False,tol=0.0001,covariance_estimator=None)[source]参数介绍:参数:priors:一个数组,数组中的元素依次指定了每个类......
  • DP读书:《材料科学基础》ALL复习考点
    材料科学基础-知识点材料科学基础难点-第五章(相图)杠杆定律一、匀晶相图二、共晶相图及其结晶三、包晶系合金相图材料科学基础(一、二、四)复习考点材料科学基础:计算题(第6章)一、结晶驱动力与过冷度的计算二、液体金属在凝固时的计算老师说,这回期末考试90%考这个,我就整......
  • 【类脑计算】突触可塑性模型之Hebbian学习规则和STDP
    1引言突触可塑性(Synapticplasticity)指经验能够修改神经回路功能的能力。特指基于活动修改突触传递强度的能力,是大脑适应新信息的主要调查机制。分为短期和长期突触可塑性,分别作用于不同时间尺度,对感官刺激的短期适应和长期行为改变及记忆存储至关重要。非对称ST......
  • docker部署wordpress个人博客
    技术:docker-compose部署wordpres和mysql,宿主机的nginx部署SSL证书将HTTPS反向代理到wordpress。使用的是ubuntu20.04准备工作:-一台云服务器,一个已经备案的域名-免费申请到的nginx的SSL证书-docker、docker-compose、nginx已部署,确认可以拉取镜像一、docker-compose部署word......