本文解决的问题: 按主题归纳 贪心算法、动态规划、多维动态规划 相关高频题型与通用解法。

适用范围: LeetCode 中文站题目,示例主要使用 Java。

阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。

贪心算法

买卖股票的最佳时机(简单)

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

提示:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

示例 1:

1
2
3
4
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

1
2
3
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}

跳跃游戏(中等)

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

示例 1:

1
2
3
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

1
2
3
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
// 55. 跳跃游戏
public boolean canJump(int[] nums) {

int max = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, i + nums[i]);
if (max <= i) {
return false;
}
}
return true;
}

跳跃游戏 II(中等)

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int jump(int[] nums) {
// 输入校验
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("Input array is null or empty");
}
int n = nums.length;
if (n == 1) {
return 0; // 如果只有一个元素,不需要跳跃
}

// 初始化变量
int currentEnd = 0; // 当前区间末尾
int farthest = 0; // 当前能到达的最远位置
int steps = 0; // 跳跃次数

for (int i = 0; i < n - 1; i++) {
// 更新最远可达位置
farthest = Math.max(farthest, i + nums[i]);

// 到达当前区间的末尾
if (i == currentEnd) {
steps++; // 需要跳跃一次
currentEnd = farthest; // 更新区间末尾

// 如果已经可以到达终点,提前返回
if (currentEnd >= n - 1) {
return steps;
}
}
}

// 如果无法到达终点,返回 -1
return -1;
}

划分字母区间(中等)

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。例如,字符串 "ababcc" 能够被分为 ["abab", "cc"],但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

提示:

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

示例 1:

1
2
3
4
5
6
输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。

示例 2:

1
2
输入:s = "eccbbbbdec"
输出:[10]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> partitionLabels(String s) {
int n=s.length();
int[] cnt=new int[26];
for(int i=0;i<n;i++)
cnt[s.charAt(i)-'a']=i;
List<Integer> ans=new ArrayList<>();
int end=0,start=0;
for(int i=0;i<n;i++){
end=Math.max(cnt[s.charAt(i)-'a'],end);
if(end==i){
ans.add(end-start+1);
start=end+1;
}
}
return ans;
}

动态规划

最长递增子序列(中等)

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

进阶:
提示:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

示例:

1
2
3
4
5
6
7
8
9
10
11
12
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}

零钱兑换(中等)

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

示例:

1
2
3
4
5
6
7
8
9
10
11
12
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

示例 2:
输入:coins = [2], amount = 3
输出:-1

示例 3:
输入:coins = [1], amount = 0
输出:0

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 0; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}

杨辉三角(简单)

给定一个非负整数 numRows, 生成「杨辉三角」的前 *numRows *行。

在「杨辉三角」中,每个数是它左上方和右上方的数的和。

3. 杨辉三角(简)示例

示例 1:

1
2
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

1
2
输入: numRows = 1
输出: [[1]]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
for (int i = 0; i < numRows; ++i) {
List<Integer> row = new ArrayList<Integer>();
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
}
}
ret.add(row);
}
return ret;
}
}

打家劫舍(中等)

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 ** 不触动警报装置的情况下 ** ,一夜之内能够偷窃到的最高金额。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

示例 1:

1
2
3
4
输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

1
2
3
4
输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
}

完全平方数(中等)

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

提示:

  • 1 <= n <= 10^4

示例 1:

1
2
3
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:

1
2
3
输入:n = 13
输出:2
解释:13 = 4 + 9

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int numSquares(int n) {
int[] dp = new int[n +1];
for (int i = 1; i <= n; i ++ ) {
int l = Integer.MAX_VALUE;
for (int j = 1; j *j <= i; j++) {
l = Math.min(dp[i - j * j], l);
}
dp[i] = l + 1;
}
return dp[n];
}
}

单词拆分(中等)

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

示例 1:

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意,你可以重复使用字典中的单词。

示例 3:

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}

最长递增子序列(中等)

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

**子序列 **是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

提示:

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

示例 1:

1
2
3
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

1
2
输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

1
2
输入:nums = [7,7,7,7,7,7,7]
输出:1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大,此时要更新 d[1],所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}

乘积最大子数组(中等)

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • nums 的任何子数组的乘积都 保证 是一个 32-位 整数

示例 1:

1
2
3
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public int maxProduct(int[] nums) {
int length = nums.length;
long[] maxF = new long[length];
long[] minF = new long[length];
for (int i = 0; i < length; i++) {
maxF[i] = nums[i];
minF[i] = nums[i];
}
for (int i = 1; i < length; ++i) {
maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
if (minF[i] < (-1 << 31)) {
minF[i] = nums[i];
}
}
int ans = (int) maxF[0];
for (int i = 1; i < length; ++i) {
ans = Math.max(ans, (int) maxF[i]);
}
return ans;
}
}

/**
易得这里的渐进时间复杂度和渐进空间复杂度都是 O(n)。

考虑优化空间。

由于第 i 个状态只和第 i−1 个状态相关,根据「滚动数组」思想,我们可以只用两个变量来维护 i−1 时刻的状态,一个维护 f max,一个维护 f min

**/
class Solution {
public:
int maxProduct(vector<int>& nums) {
long maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.size(); ++i) {
long mx = maxF, mn = minF;
maxF = max(mx * nums[i], max((long)nums[i], mn * nums[i]));
minF = min(mn * nums[i], min((long)nums[i], mx * nums[i]));
if(minF<INT_MIN) {
minF=nums[i];
}
ans = max(maxF, ans);
}
return ans;
}
};


分割等和子集(中等)

给你一个 **只包含正整数 **的 **非空 **数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

示例 1:

1
2
3
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

1
2
3
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = Math.max(maxNum, num);
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
boolean[][] dp = new boolean[n][target + 1];
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for (int i = 1; i < n; i++) {
int num = nums[i];
for (int j = 1; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n - 1][target];
}
}

/**
上述代码的空间复杂度是 O(n×target)。但是可以发现在计算 dp 的过程中,每一行的 dp 值都只与上一行的 dp 值有关,因此只需要一个一维数组即可将空间复杂度降到 O(target)。此时的转移方程为:

dp[j]=dp[j] ∣ dp[j−nums[i]]
且需要注意的是第二层的循环我们需要从大到小计算,因为如果我们从小到大更新 dp 值,那么在计算 dp[j] 值的时候,dp[j−nums[i]] 已经是被更新过的状态,不再是上一行的 dp 值。
**/
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = Math.max(maxNum, num);
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int j = target; j >= num; --j) {
dp[j] |= dp[j - num];
}
}
return dp[target];
}
}

最长有效括号(困难)

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

提示:

  • 0 <= s.length <= 3 * 10^4
  • s[i] 为 '(' 或 ')'

示例 1:

1
2
3
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"

示例 2:

1
2
3
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

示例 3:

1
2
输入:s = ""
输出:0

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.isEmpty()) {
return 0; // 处理空字符串边界条件
}

int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1); // 初始化栈底为 -1,用于计算有效括号长度

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i); // 遇到左括号,将其索引入栈
} else if (c == ')') {
if (!stack.isEmpty()) {
stack.pop(); // 遇到右括号,弹出栈顶元素
if (!stack.isEmpty()) {
// 栈不为空时,计算当前有效括号长度
maxans = Math.max(maxans, i - stack.peek());
} else {
// 栈为空时,将当前索引入栈作为新的基准
stack.push(i);
}
}
} else {
// 如果遇到非法字符,直接忽略
continue;
}
}

return maxans;
}

}

多维动态规划

最长公共子序列(中等)

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

提示:

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1:
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。

示例 2:
输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。

示例 3:
输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j -1]);
}
}
}
return dp[m][n];
}

不同路径(中等)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

示例:
2. 不同路径 (中)示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入:m = 3, n = 7
输出:28

示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:
输入:m = 7, n = 3
输出:28

示例 4:
输入:m = 3, n = 3
输出:6

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}

最长回文子串(中等)

给你一个字符串 s,找到 s 中最长的 回文 子串。

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

示例 1:

1
2
3
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

1
2
输入:s = "cbbd"
输出:"bb"

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}

int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化:所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}

char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界,左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界,就可以退出当前循环
if (j >= len) {
break;
}

if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}

// 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}

最小路径和(中等)

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明: 每次只能向下或者向右移动一步。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

示例 1:

4. 最小路径和 (中)示例

1
2
3
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:

1
2
输入:grid = [[1,2,3],[4,5,6]]
输出:12

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
}

编辑距离(中等)

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

示例 1:

1
2
3
4
5
6
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

1
2
3
4
5
6
7
8
输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();

// 有一个字符串为空串
if (n * m == 0) {
return n + m;
}

// DP 数组
int[][] D = new int[n + 1][m + 1];

// 边界状态初始化
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}

// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
left_down += 1;
}
D[i][j] = Math.min(left, Math.min(down, left_down));
}
}
return D[n][m];
}
}

参考资料