72. 编辑距离

给你两个单词 word1word2,请你计算出将 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. 0 <= word1.length, word2.length <= 500
    2. word1 和 word2 由小写英文字母组成

题解

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
/*
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数

所以,

当 word1[i] == word2[j],dp[i][j] = dp[i-1][j-1];

当 word1[i] != word2[j],dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中,dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示删除操作,dp[i][j-1] 表示插入操作。
*/
// 自底向上
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
// 第一行
for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
// 第一列
for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;

for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
return dp[n1][n2];
}
}

322. 零钱兑换

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

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

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

  • 示例 1:

    1
    2
    3
    输入:coins = [1, 2, 5], amount = 11
    输出:3
    解释:11 = 5 + 5 + 1
  • 示例 2:

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

    1
    2
    输入:coins = [1], amount = 0
    输出:0
  • 示例 4:

    1
    2
    输入:coins = [1], amount = 1
    输出:1
  • 示例 5:

    1
    2
    输入:coins = [1], amount = 2
    输出:2
  • 提示:

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

题 解

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
// 递归(直接使用会超时)
class Solution {
int res = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if(coins.length == 0){
return -1;
}

findWay(coins,amount,0);

// 如果没有任何一种硬币组合能组成总金额,返回 -1。
if(res == Integer.MAX_VALUE){
return -1;
}
return res;
}

public void findWay(int[] coins,int amount,int count){
if(amount < 0){
return;
}
if(amount == 0){
res = Math.min(res,count);
}

for(int i = 0;i < coins.length;i++){
findWay(coins,amount-coins[i],count+1);
}
}
}

343. 整数拆分

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

  • 示例 1:

    1
    2
    3
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1
  • 示例 2:

    1
    2
    3
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
  • 说明: 你可以假设 n 不小于 2 且不大于 58。

题 解

1
2
3
4
5
6
7
8
9
10
11
12
int integerBreak(int n) {
int dp[n + 1];
memset(dp, 0, sizeof(dp));
for (int i = 2; i <= n; i++) {
int curMax = 0;
for (int j = 1; j < i; j++) {
curMax = fmax(curMax, fmax(j * (i - j), j * dp[i - j]));
}
dp[i] = curMax;
}
return dp[n];
}