112. 路径总和
给你二叉树的根节点
root和一个表示目标和的整数targetSum。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
解题思路
为了解决这个问题，我们可以采用递归的方法来判断二叉树中是否存在一条从根节点到叶子节点的路径，其路径上所有节点值相加等于目标和 targetSum。这个方法的关键在于递归地减少 targetSum，直到到达叶子节点时，检查剩余的 targetSum 是否等于叶子节点的值。具体步骤如下：
- 基础情况：如果当前节点为
null，则返回false，因为我们已经到达了叶子节点的下一个位置，而没有找到符合条件的路径。 - 叶子节点判断：如果当前节点是叶子节点（即没有左右子节点），检查
targetSum是否等于当前节点的值。如果等于，则找到了一条符合条件的路径，返回true。 - 递归查找：如果当前节点不是叶子节点，递归地在左右子树中查找是否存在符合条件的路径。将
targetSum减去当前节点的值，并传给左右子节点进行递归。 - 返回结果：如果左子树或右子树的递归调用返回
true，则存在符合条件的路径，返回true；否则，返回false。
完整代码
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
// 如果是叶子节点，检查剩余的 targetSum 是否等于叶子节点的值
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
// 递归地检查左右子树
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
}Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
# 基础情况：如果当前节点为空，返回 False
if not root:
return False
# 叶子节点检查：如果是叶子节点，检查 targetSum 是否等于叶子节点的值
if not root.left and not root.right:
return root.val == targetSum
# 递归检查：递归检查左右子树，减去当前节点的值更新 targetSum
left_has_path = self.hasPathSum(root.left, targetSum - root.val)
right_has_path = self.hasPathSum(root.right, targetSum - root.val)
# 如果左右子树中任一满足条件，返回 True
return left_has_path or right_has_path115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
解题思路
我们可以定义一个二维的DP数组 dp[i][j]，其中 dp[i][j] 表示 s 的前 i 个字符中 t 的前 j 个字符作为子序列出现的次数。我们需要计算 dp[len(s)][len(t)] 的值，即整个 s 中 t 作为子序列出现的次数。
-
初始化：
- 当
j为 0，即t为空字符串时，空字符串是任何字符串的子序列，所以dp[i][0] = 1（0 <= i <= len(s)）。 - 当
i为 0，即s为空字符串时，除了t也为空字符串的情况外，s中不可能包含非空t作为子序列，所以dp[0][j] = 0（1 <= j <= len(t)）。
- 当
-
状态转移：
- 如果
s[i - 1] == t[j - 1]，那么dp[i][j]可以从dp[i - 1][j - 1]（s的前i - 1个字符中t的前j - 1个字符作为子序列出现的次数）转移过来，加上dp[i - 1][j]（即使s[i - 1]匹配上了t[j - 1]，我们也可以选择不使用s[i - 1]这个字符）。 - 如果
s[i - 1] != t[j - 1]，那么dp[i][j]只能从dp[i - 1][j]转移过来，因为s[i - 1]不能作为匹配t[j - 1]的字符。
- 如果
-
结果：
dp[len(s)][len(t)]即为最终结果。
完整代码
Java
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m + 1][n + 1];
// 初始化，当 t 为空字符串时，空字符串是任何字符串的子序列
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
// 动态规划填表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 结果取模
return dp[m][n] % (1000000007);
}
}Python
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化，当 t 为空字符串时，空字符串是任何字符串的子序列
for i in range(m + 1):
dp[i][0] = 1
# 动态规划填表
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
# 结果取模
return dp[m][n] % (10**9 + 7)120. 三角形最小路径和
给定一个三角形
triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标
i，那么下一步可以移动到下一行的下标i或i + 1。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。示例 2：
输入：triangle = [[-10]] 输出：-10
解题思路
解决这个问题，我们可以采用自底向上的动态规划方法，这样可以避免处理边界条件，使问题变得更简单。思路如下：
- 初始化：创建一个与三角形最后一行大小相同的DP数组（或直接在输入的三角形上进行操作以节省空间），用于存储到达每个位置的最小路径和。
- 自底向上计算：从三角形的倒数第二行开始，逐行向上计算每个位置的最小路径和。每个位置的最小路径和可以通过其正下方和右下方的两个位置的最小路径和加上当前位置的值得到。
- 转移方程：设
dp[i][j]表示到达三角形第i行j列位置的最小路径和，则dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]。 - 结果：经过自底向上的计算后，三角形顶部的元素（即
dp[0][0]）即为整个三角形的最小路径和。
完整代码
Java
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n];
List<Integer> lastRow = triangle.get(n - 1);
// 初始化dp数组为三角形的最后一行
for (int i = 0; i < n; i++) {
dp[i] = lastRow.get(i);
}
// 自底向上逐行计算最小路径和
for (int i = n - 2; i >= 0; i--) { // 从倒数第二行开始向上
for (int j = 0; j <= i; j++) { // 遍历当前行的每个元素
// 更新当前位置的最小路径和
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0]; // 返回三角形顶部的最小路径和
}
}Python
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
dp = triangle[-1] # 初始化dp数组为三角形的最后一行
# 自底向上逐行计算最小路径和
for i in range(n - 2, -1, -1): # 从倒数第二行开始向上
for j in range(len(triangle[i])): # 遍历当前行的每个元素
# 更新当前位置的最小路径和
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
return dp[0] # 返回三角形顶部的最小路径和
