1、解题思路动态规划：定义 dp[i] 为组成金额 i 所需的最少货币数量。初始条件： dp[0] = 0，表示组成金额 0 不需要任何货币。其他 dp[i] 初始化为 INT_MAX 或 aim + 1，表示暂时无法组成。状态转移方程： 对于每个货币面值 coin ，遍历所有金额 i 从 coin 到 aim ： dp[i] = min(dp[i], dp[i - coin] + 1)。边界条件：如果 aim 为 0，直接返回 0。如果 dp[aim] 仍为初始值，返回 -1。优化：使用一维数组 dp，空间复杂度为 O(aim)。先对货币面值排序，可以提前终止某些循环。2、代码实现C++ #...

1、解题思路动态规划：定义 dp[i] 为前 i 个数字可以解码的方式数。递推关系： 如果当前数字 s[i] 不是 '0'，则可以单独解码，dp[i] += dp[i-1]。如果前两个数字 s[i-1] 和 s[i] 组成的数字在 10 到 26 之间，则可以组合解码，dp[i] += dp[i-2]。初始条件： dp[0] = 1（空字符串有一种解码方式）。dp[1] = 1（如果第一个字符不是 '0'）。边界条件：如果字符串以 '0' 开头，直接返回 0（无法解码）。如果字符串中有 '0' 但前面无法组合（如 '30'），则直接返回 0。空间优化：使用两个变量 prev 和 curr 代替...

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] + a[i][0]（只能向下走）。dp[0][j] = dp[0][j-1] + a[0][j]（只能向右走）。空间优化： 使用滚动数组优化空间，将空间复杂度从 O(n × m) 降为 O(m) 或 O(n)。2、代码实现C++ #include <vector> class Sol...

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（表示只能向下走）。空间优化：使用滚动数组优化空间，将空间复杂度从 O(m × n) 降为 O(n) 或 O(m)。数学方法（进阶）：使用组合数学公式，路径数为 C(m+n-2, m-1) 或 C(m+n-2, n-1)。计算组合数时，可以利用乘法公式避免大数计算。2、代码实现C++ #include <vector> c...

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[0][j] = 0 和 dp[i][0] = 0（表示空字符串的公共子串长度为 0）。记录最大值和位置：在填充 dp 表格的同时，记录最大长度和对应的位置。反向构造子串：根据记录的最大长度和位置，从 str1 或 str2 中提取最长公共子串。2、代码实现C++ #include <vecto...

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-1][j], dp[i][j-1])。初始条件：dp[0][j] = 0 和 dp[i][0] = 0（表示空字符串的 LCS 长度为 0）。反向构造 LCS：从 dp[m][n] 开始，反向追踪 dp 表格，构造出 LCS。如果 str1[i-1] == str2[j-1]，则该字符属于 LCS，...

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 是数组的长度。空间优化： 由于 dp[i] 只依赖于前两个状态，可以用两个变量代替整个 dp 数组，将空间复杂度优化到 O(1)。边界条件： 如果 cost 的长度为 1，直接返回 cost[0]。如果 cost 的长度为 2，返回 min(cost[0], cost[1])。2、代码实现C++ ...

1、解题思路斐波那契数列关系：青蛙跳到第 n 级台阶的跳法数等于跳到第 n-1 级和第 n-2 级台阶的跳法数之和。这是因为青蛙可以从第 n-1 级跳 1 级上来，或者从第 n-2 级跳 2 级上来。初始条件：f(1) = 1（跳 1 级），f(2) = 2（跳 1+1 或直接跳 2 级）。迭代法（动态规划）：使用循环和变量存储中间结果，避免重复计算。时间复杂度：O(n)，空间复杂度：O(1)。矩阵快速幂法：用矩阵快速幂将时间复杂度优化到 O(log n)。适用于对时间复杂度要求更高的场景。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、...

1、解题思路递归法：直接根据斐波那契数列的定义进行递归计算。时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈深度）。不满足题目要求，但可以作为理解问题的基础。迭代法（动态规划）：使用循环和变量存储中间结果，避免重复计算。时间复杂度：O(n)，空间复杂度：O(1)。满足题目要求。矩阵快速幂法：利用矩阵快速幂将时间复杂度优化到 O(log n)。适用于对时间复杂度要求更高的场景。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return...

1、解题思路记忆化搜索与动态规划：使用深度优先搜索（DFS）遍历每个单元格，并记录从该单元格出发的最长递增路径长度。为了避免重复计算，使用一个记忆化矩阵 dp 来存储已经计算过的单元格的最长路径长度。时间复杂度：O(nm)，每个单元格最多被处理一次。空间复杂度：O(nm)，用于存储 dp 矩阵。关键步骤：对于每个单元格，检查其四个邻接单元格是否满足递增条件。递归计算邻接单元格的最长递增路径，并更新当前单元格的最长路径。使用 dp 矩阵避免重复计算。2、代码实现C++ #include <vector> class Solution { public: /** * 代码中的类名、方法...

1、解题思路回溯法：使用回溯法递归生成所有可能的括号组合。在每一步递归中，可以选择添加开括号 ( 或闭括号 ) ，但必须满足以下条件： 开括号的数量不能超过 n。闭括号的数量不能超过开括号的数量。当开括号和闭括号的数量均等于 n 时，得到一个合法组合。时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈的深度）。动态规划：可以基于动态规划的思想，利用小规模问题的解来构建大规模问题的解。这种方法的时间复杂度也是 O(2^n)，但空间复杂度略高。2、代码实现C++ #include <vector> class Solution { public: /** * 代码中的类名、方法名、...

1、解题思路回溯法：使用回溯法尝试在棋盘的每一行放置一个皇后。在放置皇后时，检查当前列和两个对角线是否已被其他皇后占用。如果当前位置安全，放置皇后并递归处理下一行。如果所有行都处理完毕，说明找到一个有效的摆放方法，计数加一。时间复杂度：O(n!)，空间复杂度：O(n)（递归栈的深度）。位运算优化：使用位运算来高效地检查列和对角线的占用情况。这种方法可以显著减少常数时间，但时间复杂度仍为 O(n!)。2、代码实现C++ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值...

1、解题思路回溯法： 使用回溯法生成所有可能的排列。在递归过程中，使用标记数组 visited 来记录哪些字符已经被使用过，避免重复使用。为了避免重复的排列，在每一层递归中跳过与前一个字符相同且未被使用的字符。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。库函数法： 使用语言内置的库函数（如 Python 的 itertools.permutations）直接生成所有排列，然后去重。简单但不符合面试要求。2、代码实现C++ #include <string> #include <vector> class Solution { public: /**...

1、解题思路深度优先搜索 (DFS)：遍历矩阵的每一个元素，当遇到一个未被访问的1时，进行DFS或BFS，标记所有相邻的1为已访问。每次发现一个新的未被访问的1，岛屿计数加一。时间复杂度：O(m*n)，空间复杂度：O(m*n)（最坏情况下递归栈的深度）。广度优先搜索 (BFS)：使用队列来实现BFS，同样遍历矩阵，遇到未被访问的1时进行BFS。时间复杂度：O(m*n)，空间复杂度：O(m*n)（队列的存储空间）。并查集 (Union-Find)：可以使用并查集来合并相邻的1，最终统计连通分量的数量。时间复杂度：O(m*n)，空间复杂度：O(m*n)。2、代码实现C++ #include &lt...