冷意

分类

/ 注册

全部文章（共170篇）

题解 | 最长上升子序列(一)

1、解题思路动态规划：定义 dp[i] 为以 arr[i] 结尾的最长严格上升子序列的长度。初始条件：每个 dp[i] 初始化为 1（因为每个元素本身就是一个长度为 1 的子序列）。状态转移方程：对于每个 i，遍历所有 j < i，如果 arr[j] < arr[i]，则 dp[i] ...

2025-06-28

0 43

题解 | 兑换零钱(一)

1、解题思路动态规划：定义 dp[i] 为组成金额 i 所需的最少货币数量。初始条件： dp[0] = 0，表示组成金额 0 不需要任何货币。其他 dp[i] 初始化为 INT_MAX 或 aim + 1，表示暂时无法组成。状态转移方程：对于每个货币面值 coin ，遍历所有金额 i 从 coin...

2025-06-28

0 55

题解 | 把数字翻译成字符串

1、解题思路动态规划：定义 dp[i] 为前 i 个数字可以解码的方式数。递推关系：如果当前数字 s[i] 不是 '0'，则可以单独解码，dp[i] += dp[i-1]。如果前两个数字 s[i-1] 和 s[i] 组成的数字在 10 到 26 之间，则可以组合解码，dp[i] += dp[i-2...

2025-06-28

0 40

题解 | 矩阵的最小路径和

1、解题思路动态规划：定义 dp[i][j] 为从 (0, 0) 到 (i, j) 的最小路径和。递推关系： dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1])。初始条件： dp[0][0] = a[0][0]。dp[i][0] = dp[i-1][0...

2025-06-28

0 43

题解 | 不同路径的数目(一)

1、解题思路动态规划：定义 dp[i][j] 为从起点 (0, 0) 到 (i, j) 的不同路径数。递推关系： dp[i][j] = dp[i-1][j] + dp[i][j-1]。初始条件： dp[0][j] = 1（表示只能向右走）。dp[i][0] = 1（表示只能向下走）。空间优化：使用滚...

2025-06-28

0 28

题解 | 最长公共子串

1、解题思路动态规划：定义 dp[i][j] 为 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子串的长度。递推关系：如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。否则，dp[i][j] = 0。初始条件：dp[...

2025-06-28

0 29

题解 | 最长公共子序列(二)

1、解题思路动态规划：定义 dp[i][j] 为 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。递推关系：如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。否则，dp[i][j] = max(dp[i-...

2025-06-28

0 40

题解 | 最小花费爬楼梯

1、解题思路动态规划：定义 dp[i] 为到达第 i 个台阶的最低花费。初始条件：dp[0] = cost[0]，dp[1] = cost[1]。递推关系：dp[i] = cost[i] + min(dp[i-1], dp[i-2])。最终结果：min(dp[n-1], dp[n-2])，其中 n...

2025-06-28

0 30

题解 | 跳台阶

1、解题思路斐波那契数列关系：青蛙跳到第 n 级台阶的跳法数等于跳到第 n-1 级和第 n-2 级台阶的跳法数之和。这是因为青蛙可以从第 n-1 级跳 1 级上来，或者从第 n-2 级跳 2 级上来。初始条件：f(1) = 1（跳 1 级），f(2) = 2（跳 1+1 或直接跳 2 级）。迭代法（...

2025-06-28

0 68

题解 | 斐波那契数列

1、解题思路递归法：直接根据斐波那契数列的定义进行递归计算。时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈深度）。不满足题目要求，但可以作为理解问题的基础。迭代法（动态规划）：使用循环和变量存储中间结果，避免重复计算。时间复杂度：O(n)，空间复杂度：O(1)。满足题目要求。矩阵快速幂法：利...

2025-06-28

0 45