精华内容
下载资源
问答
  • 2020-03-30 10:00:36

    Longest Increasing Subsequence

    给定一个无序的整数数组,找到其中最长上升子序列的长度。

    示例:
    输入: [10,9,2,5,3,7,101,18]
    输出: 4
    解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
    说明:可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。
    进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

    #python3
    class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            l=len(nums)
            if l==0:
                return 0
            dp=[1 for i in range(l)]
            for i in range(l):
                for j in range(0,i):
                    if nums[i]>nums[j]:
                        dp[i]=max(dp[i],dp[j]+1)
            return max(dp)
    
    更多相关内容
  • 动态规划和递归一样 还是要找一个出口 主要区别是要找一个列表将之间的子问题的答案储存起来 一.寻找最大值 在这个数组中,不能选相邻的 找出选出数字之和最大的数字 解: 出口: ①递归: arr = [1, 2, 4, 1, 7,...

    动态规划和递归一样
    还是要找一个出口
    主要区别是要找一个列表将之间的子问题的答案储存起来

    一.寻找最大值

    在这里插入图片描述
    在这个数组中,不能选相邻的
    找出选出数字之和最大的数字

    解:
    在这里插入图片描述
    出口:
    在这里插入图片描述
    ①递归:

    arr = [1, 2, 4, 1, 7, 8, 3]
    
    
    def rec_opt(arr, i):     # 选择第i个
        if i == 0:			# 只有第0个的话,就是他自己
            return arr[0]    
        elif i == 1:		# 第1个的话,找前两个最大的
            return max(arr[0], arr[1])
        else:				# 其他情况分为选或者不选
            A = rec_opt(arr, i - 2) + arr[i]	# 选第i的话,是他自己的权重 + 与他不相邻且之前的权重最大值
            B = rec_opt(arr, i - 1)				# 不选的话,就是前一个
            return max(A, B)					# 在选与不选之间挑一个最大的
            
    rec_opt(arr, 6)
    

    在这里插入图片描述
    ② 动态规划

    import numpy as np
    arr = [1, 2, 4, 1, 7, 8, 3]
    
    
    def dp_opt(arr):
        opt = np.zeros(len(arr))           # 储存子问题答案数组
        # 出口
        opt[0] = arr[0]
        opt[1] = max(arr[0], arr[1])
        
        # 其他情况
        for i in range(2, len(arr)):
            A = opt[i-2] + arr[i]
            B = opt[i-1]
            opt[i] = max(A, B)
            
        return opt[len(arr) - 1]
    
    dp_opt(arr)
    

    在这里插入图片描述

    二.寻找和式

    在一个数组中,我们给定一个数
    看能否在这个数组中找到一组式子之和等于给定的这个数字

    ①递归

    arr = [3, 34, 4, 12, 5, 2]
    
    def rec_subset(arr, i , s):   # 第i个,给定数字是s
        if s == 0:                # s是0,肯定能找出一个和式
            return True
        elif i == 0:              # 第0个的话,看arr[0]是否等于s,相等的话就能找出
            return arr[0] == s
        elif arr[i] > s:          # 如果arr[i] > s,继续向后找,即不选这个数
            return rec_subset(arr, i-1, s)
        else:
            A = rec_subset(arr, i-1, s-arr[i])    # 选择这个数,s把选择的数减去
            B = rec_subset(arr, i-1, s)           # 不选择这个数,s保留
            return A or B                        # 找一个能找出和式的
        
    rec_subset(arr, len(arr)-1, 9)
    

    在这里插入图片描述
    ② 动态规划
    在这里我们要定一个二维数组来储存子问题的答案
    在这里插入图片描述
    左边的表示数组中的元素
    上边的表示s,因为每次会减,所以s的可能值就是 0~9
    如果左边的能组成上边的,就是True

    import numpy as np
    
    arr = [3, 34, 4, 12, 5, 2]
    
    def dp_subset(arr, S):   # s是给定的数字
        subset = np.zeros((len(arr), S + 1), dtype = bool)
        subset[:, 0] = True              # 0列所有行都是True(都能组成0)
        subset[0, :] = False             # 0行所有列都是False
        subset[0, arr[0]] = True         # 但是0行, arr[0]是true
        
        # 填表,最右下角就是答案
        for i in range(1, len(arr)):
            for s in range(1, S+1):
                if arr[i] > s:           # 如果当前元素大于给定,不选,往后找
                    subset[i, s] = subset[i-1, s]
                else:
                    A = subset[i-1, s-arr[i]]    # 选
                    B = subset[i-1, s]           # 不选
                    subset[i,s] = A or B         # 有一个是真就行
        r, c = subset.shape            
        return subset[r-1, c-1]
    
    dp_subset(arr, 9)
    

    注:这里的能否找到,看0~i下标的元素能否组成给定数
    比如 4 虽然比 3 大,但是从 3 到 4(下标从0到2)的元素中,arr[0]是可以组成3
    的,也就是说,我们找的是从arr[0]~arr[i]的元素中能否找到数字组成给定S。
    所以我们找最右下角的意思,就是从arr[0]~arr[5]中能否找到组成9的

    在这里插入图片描述

    二.求最长子序列长度

    在这里插入图片描述
    在这里插入图片描述

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <cmath>
    #define NUM 100
    using namespace std;
    
    int son_ans[NUM][NUM];
    
    void LCSLnegth(int x_len, int y_len, const char x[], char y[])
    {
    	int i,j;
    	// 0行和0列都是0,因为只有一个元素的集合没有真子集 
    	for(i = 1;i <= x_len;i++)  son_ans[i][0] = 0;
    	for(j = 1;j <= y_len;j++)  son_ans[0][i] = 0;
    	
    	// 构造数组son_ans,最后输出右下角的答案 
    	// son_ans[i][j] 表示Xi和Yi的最长公共子序列的长度 
    	for(i = 1;i <= x_len;i++){
    		for(j = 1;j <= y_len;j++){
    			if(x[i] == y[j])
    				son_ans[i][j] = son_ans[i-1][j-1] + 1; // 之前的加上这次的
    			else if (son_ans[i-1][j] >= son_ans[i][j-1])
    				son_ans[i][j] = son_ans[i-1][j];
    			else 
    				son_ans[i][j] = son_ans[i][j-1] ;
    		}
    	}
     } 
    
    int main() 
    {
    	int x_len = 7;
    	int y_len = 6;
    	char X[x_len] = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
    	char Y[y_len] = {'B', 'D', 'C', 'A', 'B', 'A'};
    	
    	LCSLnegth(x_len, y_len, X, Y);
    	cout << son_ans[x_len][y_len];
    }           
    
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 求最长子序列的算法问题描述: 解题思路: 1.将原问题分解为子问题,并且子问题满足无后效性。 以 a[i]为终点 对应的最长序列为子问题。 2.确定状态。 maxLen(a【i】),其中a【k】为小于a【i】的数 ...

    相关概念:
    状态:子问题相关的各个变量的一组取值。
    无后效性:子问题的解取值与解题路径无关。

    动态规划:

    解题步骤:
    1.将原问题分解为子问题。
    2.确定状态。
    3.确定边界状态。
    4.确定状态转移方程。
    特点:
    1.问题具有最优子结构
    2.无后效性。

    求最长子序列的算法问题描述:

    在这里插入图片描述
    解题思路:
    1.将原问题分解为子问题,并且子问题满足无后效性。
    以 a[i]为终点 对应的最长序列为子问题。
    2.确定状态。
    maxLen(a【i】)=maxLen(a【k】)+1,其中a【k】为小于a【i】的数.
    3.确定边界状态。
    当a【i】为第一个数时,对应的maxLen=1.
    4.方程确定。
    maxLen(a【i】)=maxLen(a【k】)+1 ( i!=0)
    maxLen=1. (i>0)

    java代码:

    
    
    	/**
    	 * 
    	 * @param k   要求的以此数字为终点的子序列对应数组下标
    	 * @param arr 传入的数组
    	 * @return 最长原序列子序列长度
    	 */
    	static public int maxLen(int k, int[] arr) {
    		int j = 0; // 比arr[k]小的,且距离最近
    		int tempLen=0;
    		String temp="";
    		if (k == 1) {
    			return 1;
    		} else {              
    			for (int i = k - 1; i >= 0; i--) {
    				if (arr[i] < arr[k]) {
    					j+=1;
    					
    					temp=temp+","+Integer.toString(i);    //会多出一个逗号,如",1,2,3,4"
    					
    				}
    			}
    			if (j != 0) {
    				temp=temp.substring(1,temp.length());//去掉第一个“,”
    				String [] e=temp.split(",");  //去掉逗号存放在字符串数组
    				
    				for(String b:e) {
    					j=Integer.parseInt(b);
    					if(tempLen<maxLen(j, arr))
    					tempLen=maxLen(j, arr);
    				}
    				return  tempLen+ 1;
    			} else {
    				return 1;
    			}
    		}
    
    	
    
    
    
    展开全文
  • 最长公共子序列: 链接:https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172 题目: 我们有两个字符串m和n,如果它们的子串a和b内容相同,则称a和b是m和n的公共子序列。子串中的字符不...

    最长公共子序列:

    链接:https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172
    题目:
    我们有两个字符串m和n,如果它们的子串a和b内容相同,则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
    例如字符串“abcfbc”和“abfcab”,其中“abc”同时出现在两个字符串中,因此“abc”是它们的公共子序列。此外,“ab”、“af”等都是它们的字串。
    现在给你两个任意字符串(不包含空格),请帮忙计算它们的最长公共子序列的长度。

    题解:给定我们两个字符串求解最长的公共子序列,并且公共串是可以不连续,也就是说只要要找两个字符串公共子串的最长长度;

    如果采取暴力方法,我们可以分别求出字符串m的所有子串存于set容器中,在求出字符串n的所有子串,进行查询,找出最长的公共子串,但是这种方法的效率极低。

    所以我们将回到本篇的标题:动态规划

    1.状态定义(给定一个二维数组,数组的行代表字符m,列代表字符n)

    那我们在二维数组[ i ][ j ]的位置表示字符串m的前i个字符与字符串n的前j个字符的最长公共子串的长度

    2.状态转移:

    根据状态定义,我们知道在一个判断中无非有两种情况:第i个字符与第j个字符相同;第i个字符与第j个字符不同;

    • 第i个字符与第j个字符相同,那么[ i ][ j ]的位置可存储的数据就有两个选择,一个是[ i ][ j ],另一个是[ i-1 ][ j-1 ]+1 即表示字符串m的前i-1个字符与字符串n的前j-1个字符的最长公共子串的长度+当前位置的一个相同字符。故这种情况下状态转移方程为dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j-1]);
    • 第i个字符与第j个字符不同,我们就可以保存之前的公共子序列的最大长度,那之前的位置有谁呢?即当前位置的上面位置和左边位置即[i-1][j]   ; [i][j-1]
    • 故这种情况下状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

    3.结果:

    顾名思义:结果将保存在二维数字最右下角 

     代码:

    #include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    int main()
    {
        string str1,str2;
        while(cin>>str1>>str2)
        {
            int len1=str1.size();
            int len2=str2.size();
            vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
            //str1的前i位和str2的前j位所拥有的最大的公共字符串的个数
            for(int i=0;i<len1;++i)
            {
                for(int j=0;j<len2;++j)
                {
                    if(str1[i]==str2[j])
                    {
                        dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1]);
                    }
                    else
                    {
                        dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                    }
                }
            }
            cout<<dp[len1][len2]<<endl;
        }
        return 0;
    }

     

    展开全文
  • 最长公共子序列:X和Y的公共子序列中长度最长的(包含元素最多的)叫做X和Y的最长公共子序列。 思路: 设X=x1x2…xm和Y=y1y2…yn是两个序列,Z=z1z2…zk是这两个序列的一个最长公共子序列。 1. 如果xm=yn,那么zk=...
  • 动态规划最长子序列

    2014-05-10 11:02:26
    动态规划最长子序列
  • 动态规划——最长(连续)子序列问题0 未完成,待续1. 概述2. 最长子序列(不要求连续)3. 最长连续子序列 0 未完成,待续 1. 概述 其实本问题有两大类,一类是要求连续的,一类是要求不连续的。 先来看子序列与子串...
  • 问题描述:给定两个序列X={B,C,D,A},Y={A,B,C,B},请采用动态规划策略出其最长公共子序列,要求给出过程。解题思想:设序列X={x1,x2,...,xm}和Y={x1,x2,...,xn}的最长公共子序列Z={z1,z2,...,zk}则*若xm=yn,则zk...
  • 给定一个序列,求和为k的最长子序列最长子序列长度,c语言帮忙提供一个算法 输入一个序列,如: 1,5,6,4,2,3 输入一个整数,如:7 输出: 1 4 2 3 上述例子和为7的子序列有1,4,2 和 3,4 和 2,5 和 1,6 最长子...
  • 动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态...
  • package ... import org.apache.commons.lang3.StringUtils; import java.util.*; /** * 最长子序列 ,求子序列长度 */ public class Test3 { private static TreeSet<Strin...
  • 写程序代码,运行得到正确结果实验题目最长子序列动态规划实现实验源代码importrandomimportnumpyasnpdefinput(l,n,s):foriinrange(n):s1=s[random.ra...
  • /////////////动态规划最长子序列///////////////////// 动态规划:对大问题进行小问题分解  情况1:当前元素在比对序列存在相同元素,子序列增加,比对序列减少  情况2:当前元素在比对序列不存在相同元素...
  • 大子序列和 描述: 给定一个序列a[1],a[2],a[3]......a[n],你的工作是计算一个子序列的最大和。例如,给定(6,-1,5,4,-7),这个序列的最大和是6+(-1)+5+4=14。 输入: 输入的第一行包含一个整数T(1<=T<=...
  • 动态规划解最长公共子序列(LCS)(附详细填表过程)

    万次阅读 多人点赞 2018-11-20 12:51:34
    动态规划求解最长公共子序列: 分析规律: 做法: 伪代码: 下面演示下c数组的填表过程:(以ABCB和BDCA的LCS长度为例): 时间复杂度: 代码: 结果示例: 相关概念 子序列形式化定义: 给定一个序列X=...
  • 【问题描述】使用动态规划算法解最长公共子序列问题,具体来说就是,依据其递归式自底向上的方式依次计算得到每个子问题的优值。 【输入形式】在屏幕上输入两个序列X和Y,序列各元素数间都以一个空格分隔。 ...
  • 动态规划求序列的最长递增子序列,c++实现描述算法实现结果输出 描述 求序列的最长递增子序列 问题剖析 划分子问题 只有一个序列的时候,就是序列本身,且长度为1 序列长度大于2的时候,用L[n]数组存放每个子问题...
  • 动态规划算法通常用于求解具有某种最优性质的问题,在这类问题中,可能会有许多可行解。其思想实质是分治思想和解决冗余。适合动态规划法求解的问题,经分解得到的各个子问题往往不是相互独立的。在求解过程中,将已...
  • 主要介绍了Java实现数组最长子序列算法,涉及java针对数组的递归遍历、判断相关操作技巧,需要的朋友可以参考下
  • 求解过程使用动态规划算法打表。 先构建一个这样的表格: 然后使用双重循环对比每一个值,如果两个值相同的填写当前对角线上一个的单元格的值+1,也就是该单元格下表[行-1][列-1]的值+1。 如果两个值不相同则取...
  • 最长上升子序列(LIS) 动态规划问题的特点:当前的解又上一个阶段的解推出 当我们要求n个数的上升子...dp[i]是以i位数结尾的最长子序列个数: for(int i=0;i<n;i++){ arrL[i]=1; for(int j=0;j<i;j++){ if(arr
  • //dp[i]的值代表以nums[i]结尾的最长子序列长度 //dp[i] 所有元素置 1 //含义是每个元素都至少可以单独成为子序列,此时长度都为 1 class Solution { public int lengthOfLIS(int[] nums) { if(nums.length == 0)...
  • 动态规划解决最长公共子序列

    千次阅读 2020-03-18 10:13:46
    什么是最长公共子序列?  1. 官方定义:最长公共子序列也称作最长公共子串(不要求连续,但要求次序),英文缩写为 LCS(Longest Common ... 通俗的讲,就是给定两个字符串,出这样一个最长的公共子序列的长...
  • 为了节约重复相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。 【问题】 两字符序列的最长公共字符子序列
  • 动态规划最长子序列问题问题:给定一个序列a1,a2,a3,a4,⋯,ana_1,a_2,a_3,a_4,\cdots,a_n ,该序列中最长的子序列s1,s2,⋯,sm,(m)s_1,s_2,\cdots,s_m,(m),子序列为严格的递增序列。
  • 动态规划求字符串的公共最长子序列的长度算法 public class LongestCommonSubsequence { int lcs(char[] X, char[] Y, int m, int n) { int L[][] = new int[m + 1][n + 1]; for (int i = 0; i <= m; i+...
  • LCS与最长公共子串。 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为...
  • dp[i]表示以第i位为序列尾部的时候,序列和最大值。 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; class Solution { public: int ...
  • 如果直接用暴力的方法,适合字符串长度较小的情况,当字符串的长度很长,复杂度就会很大,那么可以用动态规划的办法解决。 设dp[i][j]表示字符串A的i号字符和B的j号字符之前的公共子序列长度; 根据A[i],B[j]的情况...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,056
精华内容 6,022
关键字:

动态规划求最长子序列