摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10952人学习

全部文章（共87篇）

题解 | #连续子数组的最大和# 来自专栏

题目的主要信息：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组的和不存在空数组，−100<=a[i]<=100-100<=a[i]<=100−100<=a[i]<=100 基本要求：时间复杂度：...

C++ 动态规划数组

2021-12-04

0 548

题解 | #连续子数组的最大和(二)# 来自专栏

题目的主要信息：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个不存在空数组返回的数组不计入空间复杂度计算基本要求：时间复杂度：O(n)O...

C++ 动态规划

2021-12-04

26 1389

题解 | #矩形覆盖# 来自专栏

题目的主要信息：可以用2∗12*12∗1的小矩形横着或者竖着去覆盖更大的矩形若用n个2∗12*12∗1的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法注意：约定 n == 0 时，输出 0 进阶要求：时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O...

C++ 递归动态规划

2021-12-03

2 683

题解 | #最长公共子串# 来自专栏

题目的主要信息：查找两个字符串str1，str2中的最长的公共子串保证str1和str2的最长公共子串存在且唯一进阶要求：时间复杂度：O(n2)O(n^2)O(n2)，空间复杂度：O(n2)O(n^2)O(n2) 方法一：暴力枚举具体做法：遍历str1每个字符作为起点，然后遍历以其为起...

C++ 动态规划

2021-12-02

1 632

题解 | #跳台阶扩展问题# 来自专栏

题目的主要信息：对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数 n为正整数，求青蛙跳上n级台阶的方案数方法一：暴力解法具体做法：对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩下的都是子问题，则数学化公式即为...

C++ 动态规划

2021-11-30

0 360

题解 | #Redraiment的走法# 来自专栏

题目的主要信息：对于一个数组，从前往后，每次只能从小到大，问最多经过多少数字即寻找最长递增子序列的长度方法一：暴力动态规划具体做法：要找到最长的递增子序列长度，常用方法是动态规划，dp[i]dp[i]dp[i]表示到元素iii结尾时，最长的子序列的长度，初始化全部为1。遍历两层，前...

C++ 动态规划二分法

2021-11-02

17 1642

题解 | #[ZJOI2010]COUNT 数字计数# 来自专栏

题目的主要信息：求在[a,b][a,b][a,b]中的所有十进制整数中，数字0-9各出现了多少次 30%的数据中，a<=b<=106a<=b<=10^6a<=b<=106，100%的数据中，a<=b<=1012a<=b<=10^12a&...

C++ 动态规划

2021-11-02

0 566

题解 | #串# 来自专栏

题目的主要信息：长度不超过nnn，且包含子序列“us”的、只由小写字母构成的字符串有多少个答案对109+710^9+7109+7取模子序列指必须u在s前，中间可以有间隔具体做法：我们可以对这个分情况讨论： dp[i][0]dp[i][0]dp[i][0]表示字符串长度为iii，但是...

C++ 动态规划

2021-11-01

1 569

题解 | #郊区春游# 来自专栏

题目的主要信息：一共nnn个点，mmm条道路连接，每条道路花费会随着道路连接情况给出给出RRR个要前往的点，前往顺序不定，问什么路线花费最少下面解法中我们用距离代替长度具体做法：首先我们用邻接矩阵来表示这个图，矩阵记录两两点之间的距离，初始化为最大值，自己到自己都是0，再根据输入更新直...

C++ 动态规划图

2021-11-01

2 555

题解 | #数位染色# 来自专栏

题目的主要信息：选出一个最高达18位数的整数nnn十进制中的一些位，这些位数字和等于没选的位的数字和如果可以输出Yes，否则输出No 具体做法：首先使用连除法将nnn的每位数字依次记录在数组中，并在这个过程中求得所有位数之和，那我们要找的就是能否在这个数组中找到诺干个数字加起来等于位数之和...

C++ 动态规划

2021-11-01

5 829