讲道理的豹子说这不是bug

分类

/ 注册

TA的专栏 99篇文章 6人订阅

刷题题解（c++）

96篇文章 900人学习

算法知识总结

3篇文章 859人学习

全部文章（共100篇）

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

方法一：动态规划1、创建一个数组dp，记录不同位置结尾的子数组和的最大值，有两种情况，其一，当前的元素单独作为一个子数组；其二，与前面的元素组成子数组，所以可以得到如下的状态转移方程：dp[i] = max(array[i], array[i] + dp[i - 1])；2、数组dp中的最大值即为连...

2023-08-27

0 292

题解 | #最长上升子序列(一)# 来自专栏

方法：动态规划1、创建一个数组dp，记录下数组arr不同位置为结尾时的最长上升子序列长度，可以得到如下的状态方程：如果存在arr[j] (j < i)小于该位置arr[i]，通过遍历前序的元素得到：dp[i] = max(dp[i], 1 + dp[j])；2、遍历完数组arr，数组dp中的最...

2023-08-27

1 319

题解 | #兑换零钱(一)# 来自专栏

方法：动态规划根据题设，求存储组成aim的最少货币数，假设该问题有解，那么最后一个组成aim的货币一定是数组arr中的元素；因此我们可以将问题拆解，通过遍历数组arr，得到组成aim - arr[i]的最少货币数，那么组成aim的最少货币数即为1 + min(aim - arr[i])。1、使用一个...

2023-08-27

0 378

题解 | #把数字翻译成字符串# 来自专栏

方法：动态规划1、遍历字符串，使用一个数组dp存储字符串不同位置结尾的译码结果次数，可以得到如下的状态转移方程如果当前字符可以和前面一个字符组成一个译码结果：dp[i] = dp[i - 1] + dp[i - 2]否则，dp[i] = dp[i - 1]2、数组最后一个元素就为字符串的译码结果次数...

2023-08-26

0 328

题解 | #矩阵的最小路径和# 来自专栏

方法：动态规划1、遍历该矩阵的所有位置，使用一个二维数组dp记录不同位置为终点时的最小路径和，可以得到如下的状态方程：不处于第一行和第一列：dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1])处于第一列不处于第一行：dp[i][j] = ...

2023-08-26

0 333

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

方法一：动态规划1、使用一个二维数组dp记录两个字符串不同位置结尾的公共子串长度，状态转移方程如下：字符相等时：dp[i][j] = 1 + dp[i - 1][j - 1]字符不相等时：dp[i][j] = 02、在遍历不同位置的同时，记录下最长的公共子串长度以及结尾的序号，可以得到最长的公共子串...

2023-08-26

1 435

题解 | #最长公共子序列(二)# 来自专栏

方法：动态规划主要分为以下两个步骤：1、获取到两个字符串s1、s2在不同位置结尾的最长公共子序列长度，用一个二维数组dp将长度存储起来；可以得到状态转移方程:如果字符相等：dp[i][j] = 1 + dp[i - 1][j - 1];如果字符不相等：dp[i][j] = max(dp[i - 1]...

2023-08-25

3 530

题解 | #最小花费爬楼梯# 来自专栏

方法：动态规划根据题设：一旦你支付此费用，即可选择向上爬一个或者两个台阶。可以将问题分解为：最后选择爬一个台阶和两个台阶这两种方案的较小值即为最小花费。时间复杂度：o(n)。空间复杂度：o(n)。 class Solution { public: int minCostClimbingS...

2023-08-12

1 372

题解 | #斐波那契数列# 来自专栏

方法一：递归斐波那契数列：f(n) = f(n-1) + f(n+1) （n>2）。可以将问题分解，使用递归解答。时间复杂度：o(2n)。空间复杂度：o(n)。递归栈深度 class Solution { public: int Fibonacci(int n) { i...

2023-08-12

1 332

题解 | #N皇后问题# 来自专栏

方法：回溯+递归按照题设可以得出：棋盘每一行有且只有一个皇后。根据该特性，使用数组res[n]记录每一行皇后所在的列数。从第一行开始，遍历每一列，判断不同列放置皇后是否有效（不能跟前面所放置的皇后列数一样，不能处于对角线）；向下递归，当到达最后一行时，摆法加1，进行回溯。时间复杂度：o(n! *...

2023-08-12

1 356