devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣刷题系列——动态规划II_力扣网刷题

作者：花生_TL007 | 2024-06-12 21:52:42

赞

踩

力扣网刷题

常见的动态规划问题(二）

本文转载于GitHub地址：https://github.com/CyC2018/CS-Notes/，仅作为个人日后复习。整合了多方面的资料，侵删。

引例解析：

内容来源于公众号文章：https://mp.weixin.qq.com/s/lKQI0aS1MBwfPujC-m_zkA

运用动态规划四部曲来进行解答：

  1. //解法一
  2. public int coinChange(int[] coins, int amount) {
  3.     // 子问题：
  4.     // f(k) = 凑出金额 k 的最小硬币数
  5.     
  6.     // f(k) = min{ 1 + f(k - c) }
  7.     // f(0) = 0
  8.     int[] dp = new int[amount+1];
  9.     Arrays.fill(dp, amount + 1); // DP 数组初始化为正无穷大
  10.     dp[0] = 0;
  11.     for (int k = 1; k <= amount; k++) {
  12.         for (int c : coins) {
  13.             if (k >= c) {
  14.                 dp[k] = Math.min(dp[k], 1 + dp[k-c]);
  15.             }
  16.         }
  17.     }
  18.     // 如果 dp[amount] > amount，认为是无效元素。
  19.     if (dp[amount] > amount) {
  20.         return -1;
  21.     } else {
  22.         return dp[amount];
  23.     }
  24. }
  25.  
  26. //解法二
  27. public int coinChange(int[] coins, int amount) {
  28.     int[] dp = new int[amount + 1];
  29.     for (int coin : coins) {
  30.         for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
  31.             if (i == coin) {
  32.                 dp[i] = 1;
  33.             } else if (dp[i] == 0 && dp[i - coin] != 0) {
  34.                 dp[i] = dp[i - coin] + 1;
  35.  
  36.             } else if (dp[i - coin] != 0) {
  37.                 dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  38.             }
  39.         }
  40.     }
  41.     return dp[amount] == 0 ? -1 : dp[amount];
  42. }

这道题进行空间优化很麻烦，所以我们忽略第四步空间优化的步骤。

  1. public int combinationSum4(int[] nums, int target) {
  2.     int[] dp = new int[target+1]; // 默认初始化为 0
  3.     dp[0] = 1; // 注意 base case
  4.     for (int k = 1; k <= target; k++) {
  5.         for (int n : nums) {
  6.             if (k >= n) {
  7.                 dp[k] += dp[k-n];
  8.             }
  9.         }
  10.     }
  11.     return dp[target];
  12. }

  1. //解法一
  2. public int change(int amount, int[] coins) {
  3.     int m = coins.length;
  4.     int[][] dp = new int[m+1][amount+1];
  5.  
  6.     for (int i = 0; i <= m; i++) {
  7.         for (int k = 0; k <= amount; k++) {
  8.             if (k == 0) {
  9.                 dp[i][k] = 1; // base case
  10.             } else if (i == 0) {
  11.                 dp[i][k] = 0; // base case
  12.             } else {
  13.                 dp[i][k] = dp[i-1][k];
  14.                 if (k >= coins[i-1]) {
  15.                     dp[i][k] += dp[i][k-coins[i-1]];
  16.                 }
  17.             }
  18.         }
  19.     }
  20.     return dp[m][amount];
  21. }
  22.  
  23. //解法二
  24. public int change(int amount, int[] coins) {
  25.     if (coins == null) {
  26.         return 0;
  27.     }
  28.     int[] dp = new int[amount + 1];
  29.     dp[0] = 1;
  30.     for (int coin : coins) {
  31.         for (int i = coin; i <= amount; i++) {
  32.             dp[i] += dp[i - coin];
  33.         }
  34.     }
  35.     return dp[amount];
  36. }

1.0-1背包问题

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

  • 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
  • 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：

  1. // W 为背包总体积
  2. // N 为物品数量
  3. // weights 数组存储 N 个物品的重量
  4. // values 数组存储 N 个物品的价值
  5. public int knapsack(int W, int N, int[] weights, int[] values) {
  6.     int[][] dp = new int[N + 1][W + 1];
  7.     for (int i = 1; i <= N; i++) {
  8.         int w = weights[i - 1], v = values[i - 1];
  9.         for (int j = 1; j <= W; j++) {
  10.             if (j >= w) {
  11.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
  12.             } else {
  13.                 dp[i][j] = dp[i - 1][j];
  14.             }
  15.         }
  16.     }
  17.     return dp[N][W];
  18. }

空间优化

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，

因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。

  1. public int knapsack(int W, int N, int[] weights, int[] values) {
  2.     int[] dp = new int[W + 1];
  3.     for (int i = 1; i <= N; i++) {
  4.         int w = weights[i - 1], v = values[i - 1];
  5.         for (int j = W; j >= 1; j--) {
  6.             if (j >= w) {
  7.                 dp[j] = Math.max(dp[j], dp[j - w] + v);
  8.             }
  9.         }
  10.     }
  11.     return dp[W];
  12. }

无法使用贪心算法的解释

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.

变种

  • 完全背包：物品数量为无限个

  • 多重背包：物品数量有限制

  • 多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制

  • 其它：物品之间相互约束或者依赖

1.1 划分数组为和相等的两部分

（力扣416）给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

题解：可以看成一个背包大小为 sum/2 的 0-1 背包问题。

代码实现：

  1. public boolean canPartition(int[] nums) {
  2.     int sum = computeArraySum(nums);
  3.     if (sum % 2 != 0) {
  4.         return false;
  5.     }
  6.     int W = sum / 2;
  7.     boolean[] dp = new boolean[W + 1];
  8.     dp[0] = true;
  9.     for (int num : nums) {                 // 0-1 背包一个物品只能用一次
  10.         for (int i = W; i >= num; i--) {   // 从后往前，先计算 dp[i] 再计算 dp[i-num]
  11.             dp[i] = dp[i] || dp[i - num];
  12.         }
  13.     }
  14.     return dp[W];
  15. }
  16.  
  17. private int computeArraySum(int[] nums) {
  18.     int sum = 0;
  19.     for (int num : nums) {
  20.         sum += num;
  21.     }
  22.     return sum;
  23. }

1.2 改变一组数的正负号使得它们的和为一给定数

（力扣494）给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

解析：该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。

可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：

  1.                   sum(P) - sum(N) = target
  2. sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
  3.                        2 * sum(P) = target + sum(nums)

因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。

代码实现：

  1. public int findTargetSumWays(int[] nums, int S) {
  2.     int sum = computeArraySum(nums);
  3.     if (sum < S || (sum + S) % 2 == 1) {
  4.         return 0;
  5.     }
  6.     int W = (sum + S) / 2;
  7.     int[] dp = new int[W + 1];
  8.     dp[0] = 1;
  9.     for (int num : nums) {
  10.         for (int i = W; i >= num; i--) {
  11.             dp[i] = dp[i] + dp[i - num];
  12.         }
  13.     }
  14.     return dp[W];
  15. }
  16.  
  17. private int computeArraySum(int[] nums) {
  18.     int sum = 0;
  19.     for (int num : nums) {
  20.         sum += num;
  21.     }
  22.     return sum;
  23. }

DFS解法：

  1. public int findTargetSumWays(int[] nums, int S) {
  2.     return findTargetSumWays(nums, 0, S);
  3. }
  4.  
  5. private int findTargetSumWays(int[] nums, int start, int S) {
  6.     if (start == nums.length) {
  7.         return S == 0 ? 1 : 0;
  8.     }
  9.     return findTargetSumWays(nums, start + 1, S + nums[start])
  10.             + findTargetSumWays(nums, start + 1, S - nums[start]);
  11. }

1.3 字符构成最多的字符串

（力扣474）在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:

给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:

输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4

解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:

输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2

解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。

代码实现：

  1. public int findMaxForm(String[] strs, int m, int n) {
  2.     if (strs == null || strs.length == 0) {
  3.         return 0;
  4.     }
  5.     int[][] dp = new int[m + 1][n + 1];
  6.     for (String s : strs) {    // 每个字符串只能用一次
  7.         int ones = 0, zeros = 0;
  8.         for (char c : s.toCharArray()) {
  9.             if (c == '0') {
  10.                 zeros++;
  11.             } else {
  12.                 ones++;
  13.             }
  14.         }
  15.         for (int i = m; i >= zeros; i--) {
  16.             for (int j = n; j >= ones; j--) {
  17.                 dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
  18.             }
  19.         }
  20.     }
  21.     return dp[m][n];
  22. }

1.4 字符串按单词列表分割

（力扣139）给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3：

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

解析：dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。

该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 "leetcode"：

["lee", "tc", "cod"]

求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。

代码实现：

  1. public boolean wordBreak(String s, List<String> wordDict) {
  2.     int n = s.length();
  3.     boolean[] dp = new boolean[n + 1];
  4.     dp[0] = true;
  5.     for (int i = 1; i <= n; i++) {
  6.         for (String word : wordDict) {   // 对物品的迭代应该放在最里层
  7.             int len = word.length();
  8.             if (len <= i && word.equals(s.substring(i - len, i))) {
  9.                 dp[i] = dp[i] || dp[i - len];
  10.             }
  11.         }
  12.     }
  13.     return dp[n];
  14. }

1.5 组合总和

（力扣377）给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。因此输出为 7。

涉及顺序的完全背包问题。

代码实现：

  1. public int combinationSum4(int[] nums, int target) {
  2.     if (nums == null || nums.length == 0) {
  3.         return 0;
  4.     }
  5.     int[] maximum = new int[target + 1];
  6.     maximum[0] = 1;
  7.     Arrays.sort(nums);
  8.     for (int i = 1; i <= target; i++) {
  9.         for (int j = 0; j < nums.length && nums[j] <= i; j++) {
  10.             maximum[i] += maximum[i - nums[j]];
  11.         }
  12.     }
  13.     return maximum[target];
  14. }

2.股票交易

2.1 需要冷却期的股票交易

（力扣309）给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

题目描述：交易之后需要有一天的冷却时间。

代码实现：

  1. public int maxProfit(int[] prices) {
  2.     if (prices == null || prices.length == 0) {
  3.         return 0;
  4.     }
  5.     int N = prices.length;
  6.     int[] buy = new int[N];
  7.     int[] s1 = new int[N];
  8.     int[] sell = new int[N];
  9.     int[] s2 = new int[N];
  10.     s1[0] = buy[0] = -prices[0];
  11.     sell[0] = s2[0] = 0;
  12.     for (int i = 1; i < N; i++) {
  13.         buy[i] = s2[i - 1] - prices[i];
  14.         s1[i] = Math.max(buy[i - 1], s1[i - 1]);
  15.         sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
  16.         s2[i] = Math.max(s2[i - 1], sell[i - 1]);
  17.     }
  18.     return Math.max(sell[N - 1], s2[N - 1]);
  19. }

2.2 需要交易费用的股票交易

（力扣714）给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

题目描述：每交易一次，都要支付一定的费用。

代码实现：

  1. public int maxProfit(int[] prices, int fee) {
  2.     int N = prices.length;
  3.     int[] buy = new int[N];
  4.     int[] s1 = new int[N];
  5.     int[] sell = new int[N];
  6.     int[] s2 = new int[N];
  7.     s1[0] = buy[0] = -prices[0];
  8.     sell[0] = s2[0] = 0;
  9.     for (int i = 1; i < N; i++) {
  10.         buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
  11.         s1[i] = Math.max(buy[i - 1], s1[i - 1]);
  12.         sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
  13.         s2[i] = Math.max(s2[i - 1], sell[i - 1]);
  14.     }
  15.     return Math.max(sell[N - 1], s2[N - 1]);
  16. }

2.3 只能进行两次的股票交易

（力扣123，hard）给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

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

代码实现：

  1. public int maxProfit(int[] prices) {
  2.     int firstBuy = Integer.MIN_VALUE, firstSell = 0;
  3.     int secondBuy = Integer.MIN_VALUE, secondSell = 0;
  4.     for (int curPrice : prices) {
  5.         if (firstBuy < -curPrice) {
  6.             firstBuy = -curPrice;
  7.         }
  8.         if (firstSell < firstBuy + curPrice) {
  9.             firstSell = firstBuy + curPrice;
  10.         }
  11.         if (secondBuy < firstSell - curPrice) {
  12.             secondBuy = firstSell - curPrice;
  13.         }
  14.         if (secondSell < secondBuy + curPrice) {
  15.             secondSell = secondBuy + curPrice;
  16.         }
  17.     }
  18.     return secondSell;
  19. }

2.4 只能进行 k 次的股票交易

（力扣188，hard）给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

代码实现：

  1. public int maxProfit(int k, int[] prices) {
  2.     int n = prices.length;
  3.     if (k >= n / 2) {   // 这种情况下该问题退化为普通的股票交易问题
  4.         int maxProfit = 0;
  5.         for (int i = 1; i < n; i++) {
  6.             if (prices[i] > prices[i - 1]) {
  7.                 maxProfit += prices[i] - prices[i - 1];
  8.             }
  9.         }
  10.         return maxProfit;
  11.     }
  12.     int[][] maxProfit = new int[k + 1][n];
  13.     for (int i = 1; i <= k; i++) {
  14.         int localMax = maxProfit[i - 1][0] - prices[0];
  15.         for (int j = 1; j < n; j++) {
  16.             maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
  17.             localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
  18.         }
  19.     }
  20.     return maxProfit[k][n - 1];
  21. }

3.字符串编辑

3.1  删除两个字符串的字符使它们相等

（力扣583）给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

可以转换为求两个字符串的最长公共子序列问题。

代码实现：

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

3.2 编辑距离

（力扣72，hard）给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

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

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

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：

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

题目描述：修改一个字符串成为另一个字符串，使得修改次数最少。一次修改操作包括：插入一个字符、删除一个字符、替换一个字符。

代码实现：

  1. public int minDistance(String word1, String word2) {
  2.     if (word1 == null || word2 == null) {
  3.         return 0;
  4.     }
  5.     int m = word1.length(), n = word2.length();
  6.     int[][] dp = new int[m + 1][n + 1];
  7.     for (int i = 1; i <= m; i++) {
  8.         dp[i][0] = i;
  9.     }
  10.     for (int i = 1; i <= n; i++) {
  11.         dp[0][i] = i;
  12.     }
  13.     for (int i = 1; i <= m; i++) {
  14.         for (int j = 1; j <= n; j++) {
  15.             if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  16.                 dp[i][j] = dp[i - 1][j - 1];
  17.             } else {
  18.                 dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
  19.             }
  20.         }
  21.     }
  22.     return dp[m][n];
  23. }

3.3 复制粘贴字符

（力扣650）最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。

示例 1:

输入: 3
输出: 3
解释:
最初, 我们只有一个字符 'A'。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 'AA'。
第 3 步, 我们使用 Paste 操作来获得 'AAA'。

代码实现：

  1. public int minSteps(int n) {
  2.     if (n == 1) return 0;
  3.     for (int i = 2; i <= Math.sqrt(n); i++) {
  4.         if (n % i == 0) return i + minSteps(n / i);
  5.     }
  6.     return n;
  7. }
  8. public int minSteps(int n) {
  9.     int[] dp = new int[n + 1];
  10.     int h = (int) Math.sqrt(n);
  11.     for (int i = 2; i <= n; i++) {
  12.         dp[i] = i;
  13.         for (int j = 2; j <= h; j++) {
  14.             if (i % j == 0) {
  15.                 dp[i] = dp[j] + dp[i / j];
  16.                 break;
  17.             }
  18.         }
  19.     }
  20.     return dp[n];
  21. }

 

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/709774
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号