力扣 673. 最长递增子序列的个数 python AC

2024-05-10 12:20

本文主要是介绍力扣 673. 最长递增子序列的个数 python AC,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划

class Solution:def findNumberOfLIS(self, nums):nums.append(float('inf'))size = len(nums)dp = [1] * sizecnt = [1] * sizefor i in range(size):for j in range(i):if nums[i] > nums[j]:if dp[i] < dp[j] + 1:dp[i] = dp[j] + 1cnt[i] = cnt[j]elif dp[i] == dp[j] + 1:cnt[i] += cnt[j]return cnt[size - 1]

状态dp[i]表示到i为止递增子序列的最大长度,cnt[i]表示到i为止达到长度dp[i]的序列数

--从0到size遍历i

  --从0到i遍历j

    --如果i数字大于j数字

      --(更新dp[i]为dp[i]和dp[j]+1中的最大值)

      --如果dp[i]小,dp[i] = dp[j]+1(到i最大长度为到j最大长度+1)

                             cnt[i] = cnt[j](到i最大长度的个数和到j最大长度的个数相等)

      --如果二者相等,cnt[i] += cnt[j](初始值为1,二者相等说明在遇到了相同最大长度的不同子序列,此时到i最大长度的个数要加上到j最大长度的子序列个数)

--返回cnt最后一个元素,即到inf的最长递增子序列个数(加入inf对个数不影响,因为一定大于前面所有数)

举例:

传入[1, 3, 5, 4, 7]

nums = [1, 3, 5, 4, 7, inf], dp = [1, 1, 1, 1, 1, 1], cnt = [1, 1, 1, 1, 1, 1]

当i=4时

dp = [1, 2, 3, 3, 1, 1], cnt = [1, 1, 1, 1, 1, 1], j = [0, 4)

j = 0, nums[4] > nums[0](7 > 1), dp[4] < dp[0] + 1(1 < 1 + 1), dp[4] = 1 + 1, cnt[4] = cnt[0](1->1)

dp = [1, 2, 3, 3, 2, 1], cnt = [1, 1, 1, 1, 1, 1]

j = 1, nums[4] > nums[1](7 > 3), dp[4] < dp[1] + 1(2 < 2 + 1), dp[4] = 2 + 1, cnt[4] = cnt[1](1->1)

dp = [1, 2, 3, 3, 3, 1], cnt = [1, 1, 1, 1, 1, 1]

j = 2, nums[4] > nums[2](7 > 5), dp[4] < dp[2] + 1(3 < 3 + 1), dp[4] = 3 + 1, cnt[4] = cnt[2](1->1)

dp = [1, 2, 3, 3, 4, 1], cnt = [1, 1, 1, 1, 1, 1]

j = 3, nums[4] > nums[3](7 > 4), dp[4] == dp[3] + 1(4 = 3 + 1), cnt[4] += cnt[3](1->2)

dp = [1, 2, 3, 3, 4, 1], cnt = [1, 1, 1, 1, 2, 1]

(太难)

这篇关于力扣 673. 最长递增子序列的个数 python AC的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/976429

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

nudepy,一个有趣的 Python 库!

更多资料获取 📚 个人网站:ipengtao.com 大家好,今天为大家分享一个有趣的 Python 库 - nudepy。 Github地址:https://github.com/hhatto/nude.py 在图像处理和计算机视觉应用中,检测图像中的不适当内容(例如裸露图像)是一个重要的任务。nudepy 是一个基于 Python 的库,专门用于检测图像中的不适当内容。该