动态规划相关高频笔试汇总

目录

一、动态规划总结

（一）基本理解

（二）应用分析

二、相关高频笔试题目练习

（一）最大子序和（Maximum Subarray）

（二）最长上升子序列（Longest Increasing Subsequence）

（三）最长公共子序列（Longest Common Subsequence）

（四）最大子数组乘积（Maximum Product Subarray）

（五）分割整数的最大乘积（Integer Break）

（六）最长有效括号（Longest Valid Parentheses）

（七）不同路径（Unique Paths）

（八）最小路径和（Minimum Path Sum）

（九）最大矩形（Maximal Rectangle）

（十）0-1背包问题（0/1 Knapsack Problem）

（十一）编辑距离（Edit Distance）

（十二）单词拆分（Word Break）

（十三）单词拆分 II（Word Break II）

（十四）单词拆分 III（Palindrome Partitioning III）

（十五）爬楼梯（Climbing Stairs）

（十六）打家劫舍（House Robber）

（十七）强盗抢劫环形街区（House Robber II）

（十八）股票买卖问题（Best Time to Buy and Sell Stock）

（十九）最佳买卖股票时机含冷冻期（Best Time to Buy and Sell Stock with Cooldown）

（二十）找零钱的最少硬币数（Coin Change）

（二十一）从起点到终点的最小路径数（Unique Paths）

干货分享，感谢您的阅读！

一、动态规划总结

（一）基本理解

动态规划（Dynamic Programming）是一种解决多阶段决策问题的优化方法。它通常用于优化具有重叠子问题结构的问题，并通过存储子问题的解来避免重复计算，从而显著提高算法的效率。

动态规划的核心思想是将原问题分解为若干个子问题，通过解决子问题并存储子问题的解来构建原问题的解。在这个过程中，动态规划利用了子问题的重叠性质，即多个子问题可能共享相同的子问题解。通过存储子问题的解，我们可以避免重复计算，从而减少算法的时间复杂度。

下面是对动态规划思想的总结分析：

  1. 最优子结构：动态规划解决的问题必须具备最优子结构的性质，即问题的最优解可以通过一系列子问题的最优解来构建。这意味着原问题的解可以通过解决子问题并结合它们的解来得到。
  2. 子问题重叠：动态规划的关键之一是子问题重叠性质，即不同的子问题可能共享相同的子问题解。通过存储子问题的解，我们可以避免重复计算，提高算法的效率。
  3. 状态转移方程：动态规划的核心是建立状态转移方程，它描述了问题的当前状态与子问题之间的关系。通过定义合适的状态和状态转移方程，我们可以将原问题划分为子问题，并通过解决子问题来构建原问题的解。
  4. 自底向上或自顶向下：在实现动态规划算法时，可以采用自底向上（Bottom-up）或自顶向下（Top-down）的方法。自底向上方法从子问题开始逐步求解并存储子问题的解，直到求解出原问题的解。自顶向下方法则从原问题开始，通过递归的方式解决子问题，并将子问题的解存储起来，避免重复计算。
  5. 存储子问题解：为了避免重复计算，动态规划通常使用数据结构（如数组、哈希表）来存储子问题的解。这样可以在需要时直接查找子问题的解，而不必重新计算。
  6. 时间空间权衡：动态规划算法往往需要额外的存储空间来存储子问题的解，以及计算状态转移方程所需的中间结果。在实际应用中，需要根据问题的规模和要求权衡时间和空间的使用，选择合适的算法实现。

总之，动态规划是一种通过划分问题为子问题并存储子问题的解来优化求解过程的算法思想。它适用于具有最优子结构和子问题重叠性质的问题。通过定义状态和状态转移方程，动态规划能够将原问题分解为子问题，并通过解决子问题来构建原问题的解。在实现动态规划算法时，可以选择自底向上或自顶向下的方法，同时需要合理地存储子问题的解以避免重复计算。尽管动态规划算法可能需要额外的存储空间，但它能够显著提高问题的求解效率。

（二）应用分析

动态规划广泛应用于各种领域，例如：

  1. 最短路径和最小生成树问题：在图论中，动态规划算法被用于求解最短路径和最小生成树等问题，如Dijkstra算法和Floyd-Warshall算法。
  2. 背包问题：动态规划被用于解决背包问题，包括0-1背包问题、无限背包问题和多重背包问题等。
  3. 字符串处理：动态规划算法可以用于字符串处理问题，如最长公共子序列（LCS）和最长递增子序列（LIS）等。
  4. 计算机视觉：在图像处理和计算机视觉领域，动态规划算法被广泛应用于图像分割、目标跟踪和图像识别等任务。
  5. 组合优化问题：动态规划也可以用于解决组合优化问题，如旅行商问题（TSP）和任务分配问题等。

需要注意的是，虽然动态规划思想能够优化问题的求解过程，但并不是所有问题都适用于动态规划方法。在实际应用中，需要仔细分析问题的性质和要求，确定是否可以使用动态规划以及选择合适的动态规划策略。

二、相关高频笔试题目练习

（一）最大子序和（Maximum Subarray）

本题直接查看数组知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中第十五题即可

（二）最长上升子序列（Longest Increasing Subsequence）

本题直接查看数组知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中第十六题即可

（三）最长公共子序列（Longest Common Subsequence）

题目描述:给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例：

输入：text1 = "abcde", text2 = "ace"  输出：3

解释：最长公共子序列是 "ace"，其长度为 3。

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法是使用动态规划来解决该问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。

  • 首先，我们需要初始化 dp 数组，将第一行和第一列的值都设为 0，表示当 text1 或 text2 的长度为 0 时，最长公共子序列的长度为 0。
  • 然后，我们可以使用双重循环遍历 text1 和 text2 的字符，逐个计算 dp 数组的值。对于每个字符 text1[i-1] 和 text2[j-1]，有两种情况：
  • 如果 text1[i-1] 等于 text2[j-1]，即当前字符相等，那么 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符可以加入最长公共子序列中；
  • 如果 text1[i-1] 不等于 text2[j-1]，即当前字符不相等，那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示当前字符不能同时出现在最长公共子序列中，需要从前一个字符的最长公共子序列长度中选择最大的值。
  • 最终，dp[m][n] 就是 text1 和 text2 的最长公共子序列的长度，其中 m 和 n 分别是 text1 和 text2 的长度。

代码展示

下面是使用动态规划解决最长公共子序列问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
  6.  * 一个字符串的子序列是指这样一个新的字符串：
  7.  * 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
  8.  * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
  9.  * 两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
  10.  * 示例：
  11.  * 输入：text1 = "abcde", text2 = "ace"    输出：3
  12.  * 解释：最长公共子序列是 "ace"，其长度为 3。
  13.  * @date 2023/5/18  23:23
  14.  */
  15. public class LongestCommonSubsequence {
  16.     public int longestCommonSubsequence(String text1, String text2) {
  17.         int m = text1.length();
  18.         int n = text2.length();
  19.         int[][] dp = new int[m + 1][n + 1];
  20.  
  21.         for (int i = 1; i <= m; i++) {
  22.             for (int j = 1; j <= n; j++) {
  23.                 if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
  24.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  25.                 } else {
  26.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  27.                 }
  28.             }
  29.         }
  30.  
  31.         return dp[m][n];
  32.     }
  33.  
  34.     public static void main(String[] args) {
  35.         String text1 = "abcde";
  36.         String text2 = "ace";
  37.         int result = new LongestCommonSubsequence().longestCommonSubsequence(text1, text2);
  38.         System.out.println("Longest Common Subsequence: " + result);
  39.  
  40.         text1 = "abc";
  41.         text2 = "def";
  42.         result = new LongestCommonSubsequence().longestCommonSubsequence(text1, text2);
  43.         System.out.println("Longest Common Subsequence: " + result);
  44.  
  45.         text1 = "AGGTAB";
  46.         text2 = "GXTXAYB";
  47.         result = new LongestCommonSubsequence().longestCommonSubsequence(text1, text2);
  48.         System.out.println("Longest Common Subsequence: " + result);
  49.  
  50.         text1 = "";
  51.         text2 = "abcdef";
  52.         result = new LongestCommonSubsequence().longestCommonSubsequence(text1, text2);
  53.         System.out.println("Longest Common Subsequence: " + result);
  54.  
  55.         text1 = "ABC";
  56.         text2 = "";
  57.         result = new LongestCommonSubsequence().longestCommonSubsequence(text1, text2);
  58.         System.out.println("Longest Common Subsequence: " + result);
  59.  
  60.         text1 = "";
  61.         text2 = "";
  62.         result = new LongestCommonSubsequence().longestCommonSubsequence(text1, text2);
  63.         System.out.println("Longest Common Subsequence: " + result);
  64.     }
  65. }

（四）最大子数组乘积（Maximum Product Subarray）

题目描述：给定一个整数数组 nums，找到数组中乘积最大的连续子数组（该子数组中至少包含一个数字），返回其乘积。

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

示例 2:输入: [-2,0,-1]         输出: 0.      解释: 结果不能为负数，乘积为 0。

来源：力扣（LeetCode）

链接：力扣

解题思路

要找到乘积最大的连续子数组，我们需要考虑乘积的正负性质。由于乘积可能存在负数，负数乘以负数会变成正数，因此我们需要同时记录最大值和最小值。

我们可以使用动态规划的方法来解决问题。

  • 定义两个变量 maxProduct 和 minProduct，分别表示当前乘积最大值和最小值。初始时，将 maxProduct 和 minProduct 都设置为数组的第一个元素 nums[0]。
  • 然后，我们遍历数组，对于每个元素 nums[i]，更新 maxProduct 和 minProduct 的值。如果当前元素为正数，则乘以 maxProduct 会得到更大的值；如果当前元素为负数，则乘以 minProduct 会得到更大的值。同时，还需要考虑当前元素自身是否大于 maxProduct，或者小于 minProduct，以保证连续性。
  • 最后，我们遍历完整个数组后，maxProduct 中存储的就是乘积最大的连续子数组的乘积。

代码展示

下面是使用动态规划解决最大子数组乘积问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个整数数组 nums，
  6.  * 找到数组中乘积最大的连续子数组（该子数组中至少包含一个数字），返回其乘积。
  7.  * 示例 1:输入: [2,3,-2,4]  输出: 6  解释: 子数组 [2,3] 有最大乘积 6。
  8.  * 示例 2:输入: [-2,0,-1]   输出: 0  解释: 结果不能为负数，乘积为 0。
  9.  * @date 2023/5/20  23:30
  10.  */
  11. public class MaximumProductSubarray {
  12.     /**
  13.      * 要找到乘积最大的连续子数组，我们需要考虑乘积的正负性质。
  14.      * 由于乘积可能存在负数，负数乘以负数会变成正数，因此我们需要同时记录最大值和最小值。
  15.      * 
  16.      * 我们可以使用动态规划的方法来解决问题。
  17.      * 定义两个变量 maxProduct 和 minProduct，分别表示当前乘积最大值和最小值。
  18.      * 初始时，将 maxProduct 和 minProduct 都设置为数组的第一个元素 nums[0]。
  19.      * 然后，我们遍历数组，对于每个元素 nums[i]，更新 maxProduct 和 minProduct 的值。
  20.      * 如果当前元素为正数，则乘以 maxProduct 会得到更大的值；
  21.      * 如果当前元素为负数，则乘以 minProduct 会得到更大的值。
  22.      * 同时，还需要考虑当前元素自身是否大于 maxProduct，或者小于 minProduct，以保证连续性。
  23.      * 最后，我们遍历完整个数组后，maxProduct 中存储的就是乘积最大的连续子数组的乘积。
  24.      */
  25.     public int maxProduct(int[] nums) {
  26.         int maxProduct = nums[0];
  27.         int minProduct = nums[0];
  28.         int result = nums[0];
  29.  
  30.         for (int i = 1; i < nums.length; i++) {
  31.             int tempMax = maxProduct;
  32.             int tempMin = minProduct;
  33.  
  34.             maxProduct = Math.max(Math.max(tempMax * nums[i], tempMin * nums[i]), nums[i]);
  35.             minProduct = Math.min(Math.min(tempMax * nums[i], tempMin * nums[i]), nums[i]);
  36.  
  37.             result = Math.max(result, maxProduct);
  38.         }
  39.  
  40.         return result;
  41.     }
  42.  
  43.     public static void main(String[] args) {
  44.         int[] nums1 = {2, 3, -2, 4};
  45.         int maxProduct1 = new MaximumProductSubarray().maxProduct(nums1);
  46.         System.out.println("最大乘积为：" + maxProduct1);
  47.  
  48.         int[] nums2 = {-2, 0, -1};
  49.         int maxProduct2 = new MaximumProductSubarray().maxProduct(nums2);
  50.         System.out.println("最大乘积为：" + maxProduct2);
  51.     }
  52. }

（五）分割整数的最大乘积（Integer Break）

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

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

示例 2:输入: 10   输出: 36      解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明：你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法采用动态规划来解决分割整数的最大乘积问题。

我们可以定义一个数组 dp，其中 dp[i] 表示将正整数 i 拆分后得到的最大乘积。

对于 i >= 2，可以将 i 拆分为两个数 j 和 i-j，然后考虑这两个数的最大乘积。

状态转移方程如下：

dp[i] = max(j * (i-j), j * dp[i-j])，其中 1 <= j < i
  • 对于 j * (i-j)，表示拆分为两个数，其中一个为 j，另一个为 i-j。
  • 对于 j * dp[i-j]，表示拆分为两个数，其中一个为 j，另一个为 i-j 的最大乘积。

最终的答案是 dp[n]，其中 n 是给定的正整数。

代码展示

下面是使用动态规划解决分割整数的最大乘积问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
  6.  * 示例 1:输入: 2     输出: 1         解释: 2 = 1 + 1, 1 × 1 = 1。
  7.  * 示例 2:输入: 10   输出: 36      解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
  8.  * 说明：你可以假设 n 不小于 2 且不大于 58。
  9.  * @date 2023/5/23  23:07
  10.  */
  11. public class IntegerBreak {
  12.     /**
  13.      * 我们可以定义一个数组 dp，其中 dp[i] 表示将正整数 i 拆分后得到的最大乘积。对于 i >= 2，可以将 i 拆分为两个数 j 和 i-j，然后考虑这两个数的最大乘积。
  14.      * 状态转移方程如下：dp[i] = max(j * (i-j), j * dp[i-j])，其中 1 <= j < i
  15.      * 对于 j * (i-j)，表示拆分为两个数，其中一个为 j，另一个为 i-j。
  16.      * 对于 j * dp[i-j]，表示拆分为两个数，其中一个为 j，另一个为 i-j 的最大乘积。
  17.      * 最终的答案是 dp[n]，其中 n 是给定的正整数。
  18.      */
  19.     public int integerBreak(int n) {
  20.         int[] dp = new int[n + 1];
  21.         dp[2] = 1;
  22.  
  23.         for (int i = 3; i <= n; i++) {
  24.             for (int j = 1; j < i; j++) {
  25.                 // 将 i 拆分为 j 和 i-j，比较 j * (i-j) 和 j * dp[i-j] 的大小
  26.                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
  27.             }
  28.         }
  29.  
  30.         return dp[n];
  31.     }
  32.  
  33.     public static void main(String[] args) {
  34.         int n1 = 2;
  35.         int maxProduct1 = new IntegerBreak().integerBreak(n1);
  36.         // 输出：最大乘积为：1
  37.         System.out.println("最大乘积为：" + maxProduct1);
  38.  
  39.         int n2 = 10;
  40.         int maxProduct2 = new IntegerBreak().integerBreak(n2);
  41.         // 输出：最大乘积为：36
  42.         System.out.println("最大乘积为：" + maxProduct2);
  43.  
  44.         int n3 = 15;
  45.         int maxProduct3 = new IntegerBreak().integerBreak(n3);
  46.         // 输出：最大乘积为：243
  47.         System.out.println("最大乘积为：" + maxProduct3);
  48.  
  49.         int n4 = 20;
  50.         int maxProduct4 = new IntegerBreak().integerBreak(n4);
  51.         // 输出：最大乘积为：1458
  52.         System.out.println("最大乘积为：" + maxProduct4);
  53.     }
  54.  
  55. }

（六）最长有效括号（Longest Valid Parentheses）

题目描述:给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:输入: "(()"        输出: 2       解释: 最长有效括号子串为 "()"

示例 2:输入: ")()())"    输出: 4      解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode）

链接：力扣

解题思路

要找到最长的包含有效括号的子串的长度，我们可以使用栈的思想来解决。

首先，我们定义一个栈和一个变量 maxLen，栈用于记录括号的索引，初始时将 -1 放入栈中，用于处理边界情况。

然后，我们遍历字符串，对于每个字符：

  • 如果是左括号 '('，将其索引入栈。
    • 如果是右括号 ')'，弹出栈顶元素表示当前右括号的匹配。
    • 如果栈为空，表示当前右括号没有匹配的左括号，将当前右括号的索引入栈，用于处理下一个可能的有效括号子串的起始位置。
    • 如果栈不为空，计算当前有效括号子串的长度，即当前右括号的索引减去栈顶元素的索引，更新 maxLen。

最后，返回 maxLen 即为最长有效括号子串的长度。

代码展示

下面是使用栈解决最长有效括号问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. import java.util.Stack;
  4.  
  5. /**
  6.  * @author yanfengzhang
  7.  * @description 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
  8.  * 示例 1:输入: "(()"        输出: 2       解释: 最长有效括号子串为 "()"
  9.  * 示例 2:输入: ")()())"    输出: 4      解释: 最长有效括号子串为 "()()"
  10.  * @date 2023/5/22  23:18
  11.  */
  12. public class LongestValidParentheses {
  13.     /**
  14.      * 要找到最长的包含有效括号的子串的长度，我们可以使用栈的思想来解决。
  15.      * 首先，我们定义一个栈和一个变量 maxLen，栈用于记录括号的索引，初始时将 -1 放入栈中，用于处理边界情况。
  16.      * 然后，我们遍历字符串，对于每个字符：
  17.      * * 如果是左括号 '('，将其索引入栈。
  18.      * * 如果是右括号 ')'，弹出栈顶元素表示当前右括号的匹配。
  19.      * * 如果栈为空，表示当前右括号没有匹配的左括号，将当前右括号的索引入栈，用于处理下一个可能的有效括号子串的起始位置。
  20.      * * 如果栈不为空，计算当前有效括号子串的长度，即当前右括号的索引减去栈顶元素的索引，更新 maxLen。
  21.      * 最后，返回 maxLen 即为最长有效括号子串的长度。
  22.      */
  23.     public int longestValidParentheses(String s) {
  24.         Stack stack = new Stack<>();
  25.         stack.push(-1);
  26.         int maxLen = 0;
  27.  
  28.         for (int i = 0; i < s.length(); i++) {
  29.             if (s.charAt(i) == '(') {
  30.                 stack.push(i);
  31.             } else {
  32.                 stack.pop();
  33.                 if (stack.isEmpty()) {
  34.                     stack.push(i);
  35.                 } else {
  36.                     maxLen = Math.max(maxLen, i - stack.peek());
  37.                 }
  38.             }
  39.         }
  40.  
  41.         return maxLen;
  42.     }
  43.  
  44.     public static void main(String[] args) {
  45.         String s1 = "(()";
  46.         int maxLen1 = new LongestValidParentheses().longestValidParentheses(s1);
  47.         System.out.println("最长有效括号子串的长度为：" + maxLen1);
  48.  
  49.         String s2 = ")()())";
  50.         int maxLen2 = new LongestValidParentheses().longestValidParentheses(s2);
  51.         System.out.println("最长有效括号子串的长度为：" + maxLen2);
  52.     }
  53. }

（七）不同路径（Unique Paths）

题目描述:一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

例如，一个 3 x 7 的网格，机器人从左上角到右下角总共有 28 条不同的路径。

注意：m 和 n 的值均不超过 100。

示例 1:输入: m = 3, n = 2.       输出: 3

解释: 从左上角开始，总共有三条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

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

来源：力扣（LeetCode）

链接：力扣

解题思路

这道题可以使用动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示从起始位置到达网格 (i, j) 的不同路径数。根据题目要求，机器人每次只能向下或向右移动，因此对于网格中的每个位置 (i, j)，可以从上方的位置 (i-1, j) 或左方的位置 (i, j-1) 到达。

根据上述分析，可以得到状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始条件为：当 i=0 或 j=0 时，只有一条路径可以到达，因此 dp[i][j] = 1。

最终要求的答案是 dp[m-1][n-1]，其中 m 和 n 分别是网格的行数和列数。

该算法的时间复杂度为 O(m * n)，空间复杂度为 O(m * n)，其中 m 和 n 分别是网格的行数和列数。通过动态规划的思想，我们可以高效地计算出不同路径的数量。

代码展示

下面是使用动态规划解决不同路径问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或向右移动一步。
  6.  * 机器人试图达到网格的右下角。问总共有多少条不同的路径？
  7.  * 例如，一个 3 x 7 的网格，机器人从左上角到右下角总共有 28 条不同的路径。
  8.  * 注意：m 和 n 的值均不超过 100。
  9.  * 示例 1:输入: m = 3, n = 2.       输出: 3
  10.  * 解释: 从左上角开始，总共有三条路径可以到达右下角。
  11.  * 1. 向右 -> 向右 -> 向下
  12.  * 2. 向右 -> 向下 -> 向右
  13.  * 3. 向下 -> 向右 -> 向右
  14.  * 示例 2:输入: m = 7, n = 3       输出: 28
  15.  * @date 2023/5/12  23:24
  16.  */
  17. public class UniquePaths {
  18.     /**
  19.      * 这道题可以使用动态规划来解决。
  20.      * 我们定义一个二维数组 dp，其中 dp[i][j] 表示从起始位置到达网格 (i, j) 的不同路径数。
  21.      * 根据题目要求，机器人每次只能向下或向右移动，
  22.      * 因此对于网格中的每个位置 (i, j)，可以从上方的位置 (i-1, j) 或左方的位置 (i, j-1) 到达。
  23.      * 
  24.      * 根据上述分析，可以得到状态转移方程：
  25.      * dp[i][j] = dp[i-1][j] + dp[i][j-1]
  26.      * 初始条件为：当 i=0 或 j=0 时，只有一条路径可以到达，因此 dp[i][j] = 1。
  27.      * 最终要求的答案是 dp[m-1][n-1]，其中 m 和 n 分别是网格的行数和列数。
  28.      * 
  29.      * 该算法的时间复杂度为 O(m * n)，空间复杂度为 O(m * n)，其中 m 和 n 分别是网格的行数和列数。
  30.      * 通过动态规划的思想，我们可以高效地计算出不同路径的数量。
  31.      */
  32.     public int uniquePaths(int m, int n) {
  33.         int[][] dp = new int[m][n];
  34.  
  35.         // 初始化第一行和第一列的路径数为1
  36.         for (int i = 0; i < m; i++) {
  37.             dp[i][0] = 1;
  38.         }
  39.         for (int j = 0; j < n; j++) {
  40.             dp[0][j] = 1;
  41.         }
  42.  
  43.         // 计算其他位置的路径数
  44.         for (int i = 1; i < m; i++) {
  45.             for (int j = 1; j < n; j++) {
  46.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  47.             }
  48.         }
  49.  
  50.         return dp[m - 1][n - 1];
  51.     }
  52.  
  53.     public static void main(String[] args) {
  54.         int m1 = 3, n1 = 2;
  55.         int paths1 = new UniquePaths().uniquePaths(m1, n1);
  56.         // 输出：不同路径的数量：3
  57.         System.out.println("不同路径的数量：" + paths1);
  58.  
  59.         int m2 = 7, n2 = 3;
  60.         int paths2 = new UniquePaths().uniquePaths(m2, n2);
  61.         // 输出：不同路径的数量：28
  62.         System.out.println("不同路径的数量：" + paths2);
  63.     }
  64.  
  65. }

（八）最小路径和（Minimum Path Sum）

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

每次只能向下或向右移动一步。

示例 1:

输入:

[

  [1,3,1],

  [1,5,1],

  [4,2,1]

]

输出: 7

解释: 路径 1→3→1→1→1 的总和最小，为 7。

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法采用动态规划的思路来解决最小路径和问题。

定义一个二维数组 dp，其中 dp[i][j] 表示从起点到网格中 (i, j) 位置的最小路径和。

根据题目要求，每次只能向下或向右移动一步，因此对于位置 (i, j)，可以从上方 (i-1, j) 或左边 (i, j-1) 这两个位置移动过来。因此，可以得到状态转移方程：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

其中 grid[i][j] 表示网格中 (i, j) 位置的数字。

接下来，可以使用动态规划的方式计算出 dp 数组的值。首先初始化边界条件，即起点 (0, 0) 的最小路径和为 grid[0][0]，然后从左上角开始遍历每个位置 (i, j)，根据状态转移方程更新 dp[i][j] 的值。

最后，返回右下角 (m-1, n-1) 位置的值 dp[m-1][n-1]，即为从左上角到右下角的最小路径和。

代码展示

下面是使用动态规划解决最小路径和问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。
  6.  * 每次只能向下或向右移动一步。
  7.  * 示例 1:
  8.  * 输入:
  9.  * [
  10.  * [1,3,1],
  11.  * [1,5,1],
  12.  * [4,2,1]
  13.  * ]
  14.  * 输出: 7
  15.  * 解释: 路径 1→3→1→1→1 的总和最小，为 7。
  16.  * @date 2023/5/12  23:31
  17.  */
  18. public class MinimumPathSum {
  19.     /**
  20.      * 最优解法采用动态规划的思路来解决最小路径和问题。
  21.      * 定义一个二维数组 dp，其中 dp[i][j] 表示从起点到网格中 (i, j) 位置的最小路径和。
  22.      * 根据题目要求，每次只能向下或向右移动一步，
  23.      * 因此对于位置 (i, j)，可以从上方 (i-1, j) 或左边 (i, j-1) 这两个位置移动过来。
  24.      * 因此，可以得到状态转移方程：
  25.      * dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
  26.      * 其中 grid[i][j] 表示网格中 (i, j) 位置的数字。
  27.      * 接下来，可以使用动态规划的方式计算出 dp 数组的值。
  28.      * 首先初始化边界条件，即起点 (0, 0) 的最小路径和为 grid[0][0]，
  29.      * 然后从左上角开始遍历每个位置 (i, j)，根据状态转移方程更新 dp[i][j] 的值。
  30.      * 最后，返回右下角 (m-1, n-1) 位置的值 dp[m-1][n-1]，即为从左上角到右下角的最小路径和。
  31.      */
  32.     public int minPathSum(int[][] grid) {
  33.         int m = grid.length;
  34.         int n = grid[0].length;
  35.  
  36.         int[][] dp = new int[m][n];
  37.  
  38.         // 初始化边界条件
  39.         dp[0][0] = grid[0][0];
  40.         for (int i = 1; i < m; i++) {
  41.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  42.         }
  43.         for (int j = 1; j < n; j++) {
  44.             dp[0][j] = dp[0][j - 1] + grid[0][j];
  45.         }
  46.  
  47.         // 计算dp数组的值
  48.         for (int i = 1; i < m; i++) {
  49.             for (int j = 1; j < n; j++) {
  50.                 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  51.             }
  52.         }
  53.  
  54.         return dp[m - 1][n - 1];
  55.     }
  56.  
  57.     public static void main(String[] args) {
  58.         int[][] grid1 = {
  59.                 {1, 3, 1},
  60.                 {1, 5, 1},
  61.                 {4, 2, 1}
  62.         };
  63.         int minSum1 = new MinimumPathSum().minPathSum(grid1);
  64.         // 输出：最小路径和为：7
  65.         System.out.println("最小路径和为：" + minSum1);
  66.  
  67.         int[][] grid2 = {
  68.                 {1, 2, 3},
  69.                 {4, 5, 6},
  70.                 {7, 8, 9}
  71.         };
  72.         int minSum2 = new MinimumPathSum().minPathSum(grid2);
  73.         // 输出：最小路径和为：21
  74.         System.out.println("最小路径和为：" + minSum2);
  75.  
  76.         int[][] grid3 = {
  77.                 {1, 2},
  78.                 {3, 4},
  79.                 {5, 6}
  80.         };
  81.         int minSum3 = new MinimumPathSum().minPathSum(grid3);
  82.         // 输出：最小路径和为：13
  83.         System.out.println("最小路径和为：" + minSum3);
  84.     }
  85. }

（九）最大矩形（Maximal Rectangle）

题目描述:给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1:

输入:

[

  ["1","0","1","0","0"],

  ["1","0","1","1","1"],

  ["1","1","1","1","1"],

  ["1","0","0","1","0"]

]

输出: 6

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法采用动态规划和柱状图的思想来解决最大矩形问题。

将问题转化为柱状图中的最大矩形问题，可以通过遍历每一行，将每一行作为底部，统计每一行上方连续的1的个数，然后计算以当前行为底部的最大矩形面积。

假设我们有一个一维数组 heights，其中的每个元素表示该列上方连续的1的个数。我们需要计算以当前行为底部的最大矩形面积。

  • 首先，初始化一个同样大小的一维数组 left，其中的元素表示当前位置左边界的索引。对于某个位置 (i, j)，如果 matrix[i][j] 是1，则 left[j] 的值为 max(left[j], curLeft)，其中 curLeft 是当前行中从左边界开始连续的1的起始位置。
  • 然后，初始化一个同样大小的一维数组 right，其中的元素表示当前位置右边界的索引。对于某个位置 (i, j)，如果 matrix[i][j] 是1，则 right[j] 的值为 min(right[j], curRight)，其中 curRight 是当前行中从右边界开始连续的1的结束位置。
  • 接下来，遍历每一行，对于每个位置 (i, j)，计算以当前位置为底部的矩形的面积为 (right[j] - left[j]) * heights[j]，并更新最大矩形面积。
  • 最后，返回最大矩形面积即可。

代码展示

下面是使用动态规划和柱状图解决最大矩形问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author yanfengzhang
  7.  * @description 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
  8.  * 示例 1:
  9.  * 输入:
  10.  * [
  11.  * ["1","0","1","0","0"],
  12.  * ["1","0","1","1","1"],
  13.  * ["1","1","1","1","1"],
  14.  * ["1","0","0","1","0"]
  15.  * ]
  16.  * 输出: 6
  17.  * @date 2023/5/21  23:37
  18.  */
  19. public class MaximalRectangle {
  20.     /**
  21.      * 最优解法采用动态规划和柱状图的思想来解决最大矩形问题。
  22.      * 将问题转化为柱状图中的最大矩形问题，可以通过遍历每一行，将每一行作为底部，统计每一行上方连续的1的个数，然后计算以当前行为底部的最大矩形面积。
  23.      * 假设我们有一个一维数组 heights，其中的每个元素表示该列上方连续的1的个数。我们需要计算以当前行为底部的最大矩形面积。
  24.      * 首先，初始化一个同样大小的一维数组 left，其中的元素表示当前位置左边界的索引。
  25.      * 对于某个位置 (i, j)，如果 matrix[i][j] 是1，则 left[j] 的值为 max(left[j], curLeft)，
  26.      * 其中 curLeft 是当前行中从左边界开始连续的1的起始位置。
  27.      * 然后，初始化一个同样大小的一维数组 right，其中的元素表示当前位置右边界的索引。
  28.      * 对于某个位置 (i, j)，如果 matrix[i][j] 是1，则 right[j] 的值为 min(right[j], curRight)，
  29.      * 其中 curRight 是当前行中从右边界开始连续的1的结束位置。
  30.      * 接下来，遍历每一行，对于每个位置 (i, j)，
  31.      * 计算以当前位置为底部的矩形的面积为 (right[j] - left[j]) * heights[j]，并更新最大矩形面积。
  32.      * 最后，返回最大矩形面积即可。
  33.      */
  34.     public int maximalRectangle(char[][] matrix) {
  35.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  36.             return 0;
  37.         }
  38.  
  39.         int m = matrix.length;
  40.         int n = matrix[0].length;
  41.  
  42.         int[] heights = new int[n];
  43.         int[] left = new int[n];
  44.         int[] right = new int[n];
  45.         // 初始化 right 数组为 n
  46.         Arrays.fill(right, n);
  47.  
  48.         int maxArea = 0;
  49.  
  50.         for (int i = 0; i < m; i++) {
  51.             int curLeft = 0, curRight = n;
  52.  
  53.             // 更新 heights 数组和 left 数组
  54.             for (int j = 0; j < n; j++) {
  55.                 if (matrix[i][j] == '1') {
  56.                     heights[j]++;
  57.                     left[j] = Math.max(left[j], curLeft);
  58.                 } else {
  59.                     heights[j] = 0;
  60.                     left[j] = 0;
  61.                     curLeft = j + 1;
  62.                 }
  63.             }
  64.  
  65.             // 更新 right 数组和计算最大矩形面积
  66.             for (int j = n - 1; j >= 0; j--) {
  67.                 if (matrix[i][j] == '1') {
  68.                     right[j] = Math.min(right[j], curRight);
  69.                     maxArea = Math.max(maxArea, (right[j] - left[j]) * heights[j]);
  70.                 } else {
  71.                     right[j] = n;
  72.                     curRight = j;
  73.                 }
  74.             }
  75.         }
  76.  
  77.         return maxArea;
  78.     }
  79.  
  80.     public static void main(String[] args) {
  81.         char[][] matrix1 = {
  82.                 {'1', '0', '1', '0', '0'},
  83.                 {'1', '0', '1', '1', '1'},
  84.                 {'1', '1', '1', '1', '1'},
  85.                 {'1', '0', '0', '1', '0'}
  86.         };
  87.         int maxArea1 = new MaximalRectangle().maximalRectangle(matrix1);
  88.         // 输出：最大矩形面积为：6
  89.         System.out.println("最大矩形面积为：" + maxArea1);
  90.  
  91.         char[][] matrix2 = {
  92.                 {'1', '1', '1', '1'},
  93.                 {'1', '1', '1', '1'},
  94.                 {'1', '1', '1', '1'}
  95.         };
  96.         int maxArea2 = new MaximalRectangle().maximalRectangle(matrix2);
  97.         // 输出：最大矩形面积为：12
  98.         System.out.println("最大矩形面积为：" + maxArea2);
  99.  
  100.         char[][] matrix3 = {
  101.                 {'0', '0', '0', '0'},
  102.                 {'0', '0', '0', '0'},
  103.                 {'0', '0', '0', '0'}
  104.         };
  105.         int maxArea3 = new MaximalRectangle().maximalRectangle(matrix3);
  106.         // 输出：最大矩形面积为：0
  107.         System.out.println("最大矩形面积为：" + maxArea3);
  108.     }
  109.  
  110. }

（十）0-1背包问题（0/1 Knapsack Problem）

题目描述:给定一个背包的容量 capacity和一组物品，每个物品有对应的重量 weights 和价值 values，要求选择一些物品放入背包中，使得放入的物品总重量不超过背包容量，并且物品的总价值最大。

注意：每个物品只能选择放入背包一次（0-1属性）。

示例：

输入:

capacity = 10

weights = [2, 3, 4, 5]

values = [3, 4, 5, 6]

输出：10

解释：选择重量为 3 和 5 的物品，它们的总重量为 8，总价值为 10，符合背包容量限制且价值最大。

来源：力扣（LeetCode）

链接：力扣

解题思路

0-1背包问题可以使用动态规划来解决。我们可以使用一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中选择，且背包容量为 j 时的最大总价值。

对于每个物品，我们有两种选择：

  1. 不选择该物品，即背包容量保持不变，总价值也不变，即 dp[i][j] = dp[i-1][j]。
  2. 选择该物品，即背包容量减去当前物品的重量，并将当前物品的价值加到总价值中，即 dp[i][j] = dp[i-1][j-weights[i]] + values[i]。

综合考虑这两种选择，可以得到状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])

初始条件为当物品数量为 0 或背包容量为 0 时，总价值为 0。

最终要求的答案是 dp[n][capacity]，其中 n 是物品的数量。

代码展示

下面是使用动态规划解决0-1背包问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个背包的容量 capacity和一组物品，
  6.  * 每个物品有对应的重量 weights 和价值 values，
  7.  * 要求选择一些物品放入背包中，使得放入的物品总重量不超过背包容量，并且物品的总价值最大。
  8.  * 注意：每个物品只能选择放入背包一次（0-1属性）。
  9.  * 示例：
  10.  * 输入:
  11.  * capacity = 10
  12.  * weights = [2, 3, 4, 5]
  13.  * values = [3, 4, 5, 6]
  14.  * 输出：13
  15.  * 解释：选择重量为 2, 3 , 5 的物品，它们的总重量为 10，总价值为 13，符合背包容量限制且价值最大。
  16.  * @date 2023/5/24  23:44
  17.  */
  18. public class KnapsackProblem {
  19.     /**
  20.      * 0-1背包问题可以使用动态规划来解决。我们可以使用一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中选择，且背包容量为 j 时的最大总价值。
  21.      * 对于每个物品，我们有两种选择：
  22.      * 1. 不选择该物品，即背包容量保持不变，总价值也不变，即 dp[i][j] = dp[i-1][j]。
  23.      * 2. 选择该物品，即背包容量减去当前物品的重量，并将当前物品的价值加到总价值中，即 dp[i][j] = dp[i-1][j-weights[i]] + values[i]。
  24.      * 综合考虑这两种选择，可以得到状态转移方程：
  25.      * dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
  26.      * 初始条件为当物品数量为 0 或背包容量为 0 时，总价值为 0。
  27.      * 最终要求的答案是 dp[n][capacity]，其中 n 是物品的数量。
  28.      */
  29.     public int knapsack(int capacity, int[] weights, int[] values) {
  30.         int n = weights.length;
  31.         int[][] dp = new int[n + 1][capacity + 1];
  32.  
  33.         // 初始化第一行和第一列为0
  34.         for (int i = 0; i <= n; i++) {
  35.             dp[i][0] = 0;
  36.         }
  37.         for (int j = 0; j <= capacity; j++) {
  38.             dp[0][j] = 0;
  39.         }
  40.  
  41.         // 计算其他位置的最大总价值
  42.         for (int i = 1; i <= n; i++) {
  43.             for (int j = 1; j <= capacity; j++) {
  44.                 if (weights[i - 1] <= j) {
  45.                     // 当前物品可以放入背包
  46.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
  47.                 } else {
  48.                     // 当前物品放不进背包
  49.                     dp[i][j] = dp[i - 1][j];
  50.                 }
  51.             }
  52.         }
  53.  
  54.         return dp[n][capacity];
  55.     }
  56.  
  57.     public static void main(String[] args) {
  58.         int capacity = 10;
  59.         int[] weights = {2, 3, 4, 5};
  60.         int[] values = {3, 4, 5, 6};
  61.  
  62.         int maxTotalValue = new KnapsackProblem().knapsack(capacity, weights, values);
  63.         // 输出：最大总价值：13
  64.         System.out.println("最大总价值：" + maxTotalValue);
  65.     }
  66. }

（十一）编辑距离（Edit Distance）

题目描述:给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

可以对一个单词执行以下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 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')

来源：力扣（LeetCode）

链接：力扣

解题思路

这道题可以使用动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需要的最少操作数。

考虑到转换过程中的三种操作：插入、删除和替换。我们可以分别考虑这三种操作对应的子问题：

  1. 插入操作：将 word1 的前 i 个字符转换为 word2 的前 j-1 个字符，然后插入一个字符得到 word2 的前 j 个字符。
  2. 删除操作：将 word1 的前 i-1 个字符转换为 word2 的前 j 个字符，然后删除 word1 的第 i 个字符。
  3. 替换操作：将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符，然后将 word1 的第 i 个字符替换为 word2 的第 j 个字符。

根据上述分析，可以得到状态转移方程：

  1. dp[i][j] = min(dp[i][j-1] + 1,   // 插入操作
  2.  
  3.                dp[i-1][j] + 1,   // 删除操作
  4.  
  5.                dp[i-1][j-1] + cost)  // 替换操作

其中，cost 表示 word1 的第 i 个字符和 word2 的第 j 个字符是否相等。如果相等，则 cost 为 0，否则为 1。

初始条件为：当其中一个字符串为空时，转换的操作数为另一个字符串的长度。

最终要求的答案是 dp[m][n]，其中 m 和 n 分别是 word1 和 word2 的长度。

代码展示

下面是使用动态规划解决编辑距离问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
  6.  * 可以对一个单词执行以下三种操作：
  7.  * 1. 插入一个字符
  8.  * 2. 删除一个字符
  9.  * 3. 替换一个字符
  10.  * 示例 1:输入: word1 = "horse", word2 = "ros”.   输出: 3
  11.  * 解释:
  12.  * horse -> rorse (将 'h' 替换为 'r')
  13.  * rorse -> rose (删除 'r')
  14.  * rose -> ros (删除 'e')
  15.  * 示例 2:输入: word1 = "intention", word2 = "execution”.  输出: 5
  16.  * 解释:
  17.  * intention -> inention (删除 't')
  18.  * inention -> enention (将 'i' 替换为 'e')
  19.  * enention -> exention (将 'n' 替换为 'x')
  20.  * exention -> exection (将 'n' 替换为 'c')
  21.  * exection -> execution (插入 'u')
  22.  * @date 2023/5/26  23:50
  23.  */
  24. public class EditDistance {
  25.     /**
  26.      * 这道题可以使用动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需要的最少操作数。
  27.      * 考虑到转换过程中的三种操作：插入、删除和替换。我们可以分别考虑这三种操作对应的子问题：
  28.      * 1. 插入操作：将 word1 的前 i 个字符转换为 word2 的前 j-1 个字符，然后插入一个字符得到 word2 的前 j 个字符。
  29.      * 2. 删除操作：将 word1 的前 i-1 个字符转换为 word2 的前 j 个字符，然后删除 word1 的第 i 个字符。
  30.      * 3. 替换操作：将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符，然后将 word1 的第 i 个字符替换为 word2 的第 j 个字符。
  31.      * 根据上述分析，可以得到状态转移方程：
  32.      * dp[i][j] = min(dp[i][j-1] + 1,   // 插入操作
  33.      * dp[i-1][j] + 1,   // 删除操作
  34.      * dp[i-1][j-1] + cost)  // 替换操作
  35.      * 其中，cost 表示 word1 的第 i 个字符和 word2 的第 j 个字符是否相等。如果相等，则 cost 为 0，否则为 1。
  36.      * 初始条件为：当其中一个字符串为空时，转换的操作数为另一个字符串的长度。
  37.      * 最终要求的答案是 dp[m][n]，其中 m 和 n 分别是 word1 和 word2 的长度。
  38.      */
  39.     public int minDistance(String word1, String word2) {
  40.         int m = word1.length();
  41.         int n = word2.length();
  42.  
  43.         int[][] dp = new int[m + 1][n + 1];
  44.  
  45.         // 初始化第一行和第一列
  46.         for (int i = 0; i <= m; i++) {
  47.             dp[i][0] = i;
  48.         }
  49.         for (int j = 0; j <= n; j++) {
  50.             dp[0][j] = j;
  51.         }
  52.  
  53.         // 计算其他位置的最小操作数
  54.         for (int i = 1; i <= m; i++) {
  55.             for (int j = 1; j <= n; j++) {
  56.                 int cost = (word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1;
  57.                 dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + cost));
  58.             }
  59.         }
  60.  
  61.         return dp[m][n];
  62.     }
  63.  
  64.     public static void main(String[] args) {
  65.         String word1 = "horse";
  66.         String word2 = "ros";
  67.         int minOps1 = new EditDistance().minDistance(word1, word2);
  68.         // 输出：将 "horse" 转换为 "ros" 的最少操作数：3
  69.         System.out.println("将 \"" + word1 + "\" 转换为 \"" + word2 + "\" 的最少操作数：" + minOps1);
  70.  
  71.         String word3 = "intention";
  72.         String word4 = "execution";
  73.         int minOps2 = new EditDistance().minDistance(word3, word4);
  74.         // 输出：将 "intention" 转换为 "execution" 的最少操作数：5
  75.         System.out.println("将 \"" + word3 + "\" 转换为 \"" + word4 + "\" 的最少操作数：" + minOps2);
  76.     }
  77. }

（十二）单词拆分（Word Break）

题目描述:给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 字典中的单词可以重复使用。
  • 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]    输出: true

解释: "leetcode" 可以被拆分为 "leet" 和 "code" 这两个单词。

示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen”].     输出: true

解释: "applepenapple" 可以被拆分为 "apple", "pen" 和 "apple" 这三个单词。

注意你可以重复使用字典中的单词。

来源：力扣（LeetCode）

链接：力扣

解题思路

单词拆分问题可以使用动态规划来解决。

  • 我们可以使用一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分为字典中的单词。
  • 初始条件为 dp[0] = true，表示空字符串可以被拆分。
  • 然后，我们可以通过遍历字符串的每个位置 i，并在每个位置检查是否存在可拆分的位置 j（j 小于 i），使得字符串从位置 j 到位置 i 的子串在字典中存在。如果存在这样的 j，且 dp[j] 为 true，则说明从位置 j 到位置 i 的子串可以被拆分为字典中的单词，因此将 dp[i] 设置为 true。
  • 最终，dp[s.length()] 即为判断字符串 s 是否可以被拆分的结果。

该算法的时间复杂度为 O(n^2)，其中 n 是字符串 s 的长度。通过动态规划的思想，我们可以在一次遍历中计算出是否可以将字符串拆分为字典中的单词。

代码展示

下面是使用动态规划解决单词拆分问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. import java.util.Arrays;
  4. import java.util.List;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
  9.  * 说明：
  10.  * * 字典中的单词可以重复使用。
  11.  * * 你可以假设字典中没有重复的单词。
  12.  * 示例 1：
  13.  * 输入: s = "leetcode", wordDict = ["leet", "code"]  输出: true
  14.  * 解释: "leetcode" 可以被拆分为 "leet" 和 "code" 这两个单词。
  15.  * 示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen”]. 输出: true
  16.  * 解释: "applepenapple" 可以被拆分为 "apple", "pen" 和 "apple" 这三个单词。
  17.  * 注意你可以重复使用字典中的单词。
  18.  * @date 2023/5/11  23:55
  19.  */
  20. public class WordBreak {
  21.     /**
  22.      * 单词拆分问题可以使用动态规划来解决。我们可以使用一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分为字典中的单词。
  23.      * 初始条件为 dp[0] = true，表示空字符串可以被拆分。
  24.      * 然后，我们可以通过遍历字符串的每个位置 i，并在每个位置检查是否存在可拆分的位置 j（j 小于 i），使得字符串从位置 j 到位置 i 的子串在字典中存在。
  25.      * 如果存在这样的 j，且 dp[j] 为 true，则说明从位置 j 到位置 i 的子串可以被拆分为字典中的单词，因此将 dp[i] 设置为 true。
  26.      * 最终，dp[s.length()] 即为判断字符串 s 是否可以被拆分的结果。
  27.      * 
  28.      * 该算法的时间复杂度为 O(n^2)，其中 n 是字符串 s 的长度。
  29.      * 通过动态规划的思想，我们可以在一次遍历中计算出是否可以将字符串拆分为字典中的单词。
  30.      */
  31.     public boolean wordBreak(String s, List wordDict) {
  32.         int n = s.length();
  33.         boolean[] dp = new boolean[n + 1];
  34.         dp[0] = true;
  35.  
  36.         for (int i = 1; i <= n; i++) {
  37.             for (int j = 0; j < i; j++) {
  38.                 // 检查位置 j 到位置 i 的子串是否在字典中
  39.                 if (dp[j] && wordDict.contains(s.substring(j, i))) {
  40.                     dp[i] = true;
  41.                     break;
  42.                 }
  43.             }
  44.         }
  45.  
  46.         return dp[n];
  47.     }
  48.  
  49.     public static void main(String[] args) {
  50.         String s1 = "leetcode";
  51.         List wordDict1 = Arrays.asList("leet", "code");
  52.         boolean canBreak1 = new WordBreak().wordBreak(s1, wordDict1);
  53.         // 输出：是否可以拆分：true
  54.         System.out.println("是否可以拆分：" + canBreak1);
  55.  
  56.         String s2 = "applepenapple";
  57.         List wordDict2 = Arrays.asList("apple", "pen");
  58.         boolean canBreak2 = new WordBreak().wordBreak(s2, wordDict2);
  59.         // 输出：是否可以拆分：true
  60.         System.out.println("是否可以拆分：" + canBreak2);
  61.  
  62.         String s3 = "catsandog";
  63.         List wordDict3 = Arrays.asList("cats", "dog", "sand", "and", "cat");
  64.         boolean canBreak3 = new WordBreak().wordBreak(s3, wordDict3);
  65.         // 输出：是否可以拆分：false
  66.         System.out.println("是否可以拆分：" + canBreak3);
  67.     }
  68.  
  69. }

（十三）单词拆分 II（Word Break II）

题目描述:给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，为 s 添加空格，使其成为一个句子中的单词拼接，返回所有可能的句子。

说明：

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

示例 1:

输入:

s = "catsanddog"

wordDict = ["cat", "cats", "and", "sand", "dog"]

输出:

[

  "cats and dog",

  "cat sand dog"

]

示例 2:

输入:

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

输出:

[

  "pine apple pen apple",

  "pineapple pen apple",

  "pine applepen apple"

]

解释: 注意你可以重复使用字典中的单词。

示例 3:

输入:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

输出:

[]

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法采用动态规划和回溯的结合来解决单词拆分 II 问题。

  • 首先使用动态规划判断给定的字符串 s 是否可以被拆分成字典中的单词。可以使用一个布尔数组 dp，其中 dp[i] 表示从字符串的开头到第 i 个字符（不包含第 i 个字符）的子串是否可以被拆分成字典中的单词。初始化时，将 dp[0] 设置为 true，表示空字符串可以被拆分。
  • 然后，使用回溯算法生成所有可能的句子。对于给定的字符串 s，从开头开始逐个字符进行遍历。对于每个遍历到的位置 i，如果 dp[i] 为 true，则说明从开头到第 i 个字符的子串可以被拆分成字典中的单词。接下来，需要递归生成剩余部分的句子，并将其与当前单词拼接起来形成完整的句子。

为了避免重复计算，可以使用一个哈希表 memo 来存储已经计算过的位置，以及对应的生成的句子列表。

代码展示

下面是使用动态规划和回溯解决单词拆分 II 问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;
  6. import java.util.HashSet;
  7. import java.util.List;
  8. import java.util.Map;
  9. import java.util.Set;
  10.  
  11. /**
  12.  * @author yanfengzhang
  13.  * @description 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，为 s 添加空格，使其成为一个句子中的单词拼接，返回所有可能的句子。
  14.  * 说明：
  15.  * * 拆分时可以重复使用字典中的单词。
  16.  * * 你可以假设字典中没有重复的单词。
  17.  * 示例 1:
  18.  * 输入:
  19.  * s = "catsanddog"
  20.  * wordDict = ["cat", "cats", "and", "sand", "dog"]
  21.  * 输出:
  22.  * [
  23.  * "cats and dog",
  24.  * "cat sand dog"
  25.  * ]
  26.  * 示例 2:
  27.  * 输入:
  28.  * s = "pineapplepenapple"
  29.  * wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
  30.  * 输出:
  31.  * [
  32.  * "pine apple pen apple",
  33.  * "pineapple pen apple",
  34.  * "pine applepen apple"
  35.  * ]
  36.  * 解释: 注意你可以重复使用字典中的单词。
  37.  * 示例 3:
  38.  * 输入:
  39.  * s = "catsandog"
  40.  * wordDict = ["cats", "dog", "sand", "and", "cat"]
  41.  * 输出:
  42.  * []
  43.  * @date 2023/5/11  23:08
  44.  */
  45. public class WordBreakII {
  46.     /**
  47.      * 最优解法采用动态规划和回溯的结合来解决单词拆分 II 问题。
  48.      * 首先使用动态规划判断给定的字符串 s 是否可以被拆分成字典中的单词。
  49.      * 可以使用一个布尔数组 dp，其中 dp[i] 表示从字符串的开头到第 i 个字符（不包含第 i 个字符）的子串是否可以被拆分成字典中的单词。
  50.      * 初始化时，将 dp[0] 设置为 true，表示空字符串可以被拆分。
  51.      * 然后，使用回溯算法生成所有可能的句子。
  52.      * 对于给定的字符串 s，从开头开始逐个字符进行遍历。
  53.      * 对于每个遍历到的位置 i，如果 dp[i] 为 true，则说明从开头到第 i 个字符的子串可以被拆分成字典中的单词。
  54.      * 接下来，需要递归生成剩余部分的句子，并将其与当前单词拼接起来形成完整的句子。
  55.      * 为了避免重复计算，可以使用一个哈希表 memo 来存储已经计算过的位置，以及对应的生成的句子列表。
  56.      */
  57.     public List wordBreak(String s, List wordDict) {
  58.         Set wordSet = new HashSet<>(wordDict);
  59.         Map> memo = new HashMap<>();
  60.  
  61.         return backtrack(s, 0, wordSet, memo);
  62.     }
  63.  
  64.     private List backtrack(String s, int start, Set wordSet, Map> memo) {
  65.         if (memo.containsKey(start)) {
  66.             return memo.get(start);
  67.         }
  68.  
  69.         List sentences = new ArrayList<>();
  70.         if (start == s.length()) {
  71.             sentences.add("");
  72.         }
  73.  
  74.         for (int end = start + 1; end <= s.length(); end++) {
  75.             String word = s.substring(start, end);
  76.             if (wordSet.contains(word)) {
  77.                 List nextSentences = backtrack(s, end, wordSet, memo);
  78.                 for (String nextSentence : nextSentences) {
  79.                     sentences.add(word + (nextSentence.isEmpty() ? "" : " ") + nextSentence);
  80.                 }
  81.             }
  82.         }
  83.  
  84.         memo.put(start, sentences);
  85.         return sentences;
  86.     }
  87.  
  88.     public static void main(String[] args) {
  89.         String s1 = "catsanddog";
  90.         List wordDict1 = Arrays.asList("cat", "cats", "and", "sand", "dog");
  91.         List sentences1 = new WordBreakII().wordBreak(s1, wordDict1);
  92.         System.out.println("所有可能的句子：");
  93.         for (String sentence : sentences1) {
  94.             System.out.println(sentence);
  95.         }
  96.         System.out.println();
  97.  
  98.         String s2 = "pineapplepenapple";
  99.         List wordDict2 = Arrays.asList("apple", "pen", "applepen", "pine", "pineapple");
  100.         List sentences2 = new WordBreakII().wordBreak(s2, wordDict2);
  101.         System.out.println("所有可能的句子：");
  102.         for (String sentence : sentences2) {
  103.             System.out.println(sentence);
  104.         }
  105.         System.out.println();
  106.  
  107.         String s3 = "catsandog";
  108.         List wordDict3 = Arrays.asList("cats", "dog", "sand", "and", "cat");
  109.         List sentences3 = new WordBreakII().wordBreak(s3, wordDict3);
  110.         System.out.println("所有可能的句子：");
  111.         for (String sentence : sentences3) {
  112.             System.out.println(sentence);
  113.         }
  114.     }
  115. }

（十四）单词拆分 III（Palindrome Partitioning III）

题目描述:给定一个字符串 s，将 s 分割成若干个非空子串，使得每个子串都是回文串。计算将字符串 s 分割成回文分割所需的最小分割次数。

示例 1:输入: s = "aab”.   输出: 1

解释: 将字符串 "aab" 分割成 ["aa","b"]，其中 "aa" 是回文串，所以只需要进行一次分割。

示例 2:输入: s = "leetcode"    输出: 2

解释: 将字符串 "leetcode" 分割成 ["leet","code"]，其中 "leet" 和 "code" 都是回文串，所以需要进行两次分割。

来源：力扣（LeetCode）

链接：力扣

解题思路

这个问题可以使用动态规划来解决。首先，我们可以使用动态规划来计算任意子串是否是回文串，以便我们可以在后续的计算中使用。

  • 我们定义一个二维数组 dp，其中 dp[i][j] 表示将子串 s[i:j] 分割成回文子串所需的最小分割次数。
  • 初始化数组 dp 为无穷大，除了 dp[i][i] = 0，表示单个字符是回文串，不需要进行分割。
  • 然后，我们从长度为 2 的子串开始，逐步增加子串的长度，进行动态规划计算。对于每个子串 s[i:j]，我们枚举一个分割点 k，将子串分割成两部分 s[i:k] 和 s[k+1:j]，如果 s[i:k] 是回文串，则可以将其分割为一个回文子串，然后在 dp[i][j] 的基础上加 1，得到 dp[i][k] + dp[k+1][j] + 1。
  • 最后，dp[0][n-1] 就是将整个字符串分割成回文子串所需的最小分割次数，其中 n 是字符串的长度。

代码展示

下面是使用动态规划解决单词拆分 III问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author yanfengzhang
  7.  * @description 给定一个字符串 s，将 s 分割成若干个非空子串，使得每个子串都是回文串。
  8.  * 计算将字符串 s 分割成回文分割所需的最小分割次数。
  9.  * 示例 1:输入: s = "aab”.   输出: 1
  10.  * 解释: 将字符串 "aab" 分割成 ["aa","b"]，其中 "aa" 是回文串，所以只需要进行一次分割。
  11.  * 示例 2:输入: s = "leetcode"    输出: 2
  12.  * 解释: 将字符串 "leetcode" 分割成 ["leet","code"]，其中 "leet" 和 "code" 都是回文串，所以需要进行两次分割。
  13.  * @date 2023/5/17  23:17
  14.  */
  15. public class PalindromePartitioningIII {
  16.     /**
  17.      * 这个问题可以使用动态规划来解决。首先，我们可以使用动态规划来计算任意子串是否是回文串，以便我们可以在后续的计算中使用。
  18.      * 我们定义一个二维数组 dp，其中 dp[i][j] 表示将子串 s[i:j] 分割成回文子串所需的最小分割次数。
  19.      * 初始化数组 dp 为无穷大，除了 dp[i][i] = 0，表示单个字符是回文串，不需要进行分割。
  20.      * 然后，我们从长度为 2 的子串开始，逐步增加子串的长度，进行动态规划计算。
  21.      * 对于每个子串 s[i:j]，我们枚举一个分割点 k，将子串分割成两部分 s[i:k] 和 s[k+1:j]，如果 s[i:k] 是回文串，则可以将其分割为一个回文子串，
  22.      * 然后在 dp[i][j] 的基础上加 1，得到 dp[i][k] + dp[k+1][j] + 1。
  23.      * 最后，dp[0][n-1] 就是将整个字符串分割成回文子串所需的最小分割次数，其中 n 是字符串的长度。
  24.      */
  25.     public int palindromePartition(String s, int k) {
  26.         int n = s.length();
  27.         int[][] dp = new int[n][n];
  28.  
  29.         for (int len = 2; len <= n; len++) {
  30.             for (int i = 0; i + len <= n; i++) {
  31.                 int j = i + len - 1;
  32.                 dp[i][j] = getPalindromeCount(s, i, j);
  33.             }
  34.         }
  35.  
  36.         int[][] dp2 = new int[n + 1][k + 1];
  37.         for (int i = 0; i <= n; i++) {
  38.             Arrays.fill(dp2[i], Integer.MAX_VALUE / 2);
  39.         }
  40.         dp2[0][0] = 0;
  41.  
  42.         for (int i = 1; i <= n; i++) {
  43.             for (int j = 1; j <= Math.min(i, k); j++) {
  44.                 for (int p = 0; p < i; p++) {
  45.                     dp2[i][j] = Math.min(dp2[i][j], dp2[p][j - 1] + dp[p][i - 1]);
  46.                 }
  47.             }
  48.         }
  49.  
  50.         return dp2[n][k];
  51.     }
  52.  
  53.     private int getPalindromeCount(String s, int i, int j) {
  54.         int count = 0;
  55.         while (i < j) {
  56.             if (s.charAt(i) != s.charAt(j)) {
  57.                 count++;
  58.             }
  59.             i++;
  60.             j--;
  61.         }
  62.         return count;
  63.     }
  64.  
  65.     public static void main(String[] args) {
  66.         String s1 = "aab";
  67.         int k1 = 1;
  68.         int minCuts1 = new PalindromePartitioningIII().palindromePartition(s1, k1);
  69.         System.out.println("将字符串 " + s1 + " 分割成回文子串所需的最小分割次数为：" + minCuts1);
  70.  
  71.         String s2 = "leetcode";
  72.         int k2 = 2;
  73.         int minCuts2 = new PalindromePartitioningIII().palindromePartition(s2, k2);
  74.         System.out.println("将字符串 " + s2 + " 分割成回文子串所需的最小分割次数为：" + minCuts2);
  75.     }
  76. }

（十五）爬楼梯（Climbing Stairs）

题目描述:假设你正在爬楼梯。需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。编写一个函数，计算你到达楼顶的不同方式的数量。

注意：给定的 n 是一个正整数。

示例 1:输入: 2   输出: 2

解释: 有两种方式可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2:输入: 3   输出: 3

解释: 有三种方式可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

来源：力扣（LeetCode）

链接：力扣

解题思路

这道题可以使用动态规划来解决。我们定义一个数组 dp，其中 dp[i] 表示爬到第 i 阶楼梯的不同方式的数量。根据题目要求，爬到第 i 阶楼梯的方式只有两种：

  1. 从第 i-1 阶楼梯爬一步到达：dp[i-1]
  2. 从第 i-2 阶楼梯爬两步到达：dp[i-2]

所以，dp[i] = dp[i-1] + dp[i-2]，即爬到第 i 阶楼梯的不同方式数量等于爬到第 i-1 阶和第 i-2 阶楼梯方式数量之和。

初始条件是 dp[0] = 1（表示不爬任何台阶）和 dp[1] = 1（表示爬一阶台阶）。

最终要求的答案是 dp[n]，其中 n 表示楼梯的总阶数。

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是楼梯的总阶数。通过动态规划的思想，我们可以高效地计算出爬楼梯的不同方式的数量。

代码展示

下面是使用动态规划解决爬楼梯问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 假设你正在爬楼梯。需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。
  6.  * 编写一个函数，计算你到达楼顶的不同方式的数量。
  7.  * 注意：给定的 n 是一个正整数。
  8.  * 示例 1:输入: 2   输出: 2
  9.  * 解释: 有两种方式可以爬到楼顶。
  10.  * 1. 1 阶 + 1 阶
  11.  * 2. 2 阶
  12.  * 示例 2:输入: 3   输出: 3
  13.  * 解释: 有三种方式可以爬到楼顶。
  14.  * 1. 1 阶 + 1 阶 + 1 阶
  15.  * 2. 1 阶 + 2 阶
  16.  * 3. 2 阶 + 1 阶
  17.  * @date 2023/5/27  23:36
  18.  */
  19. public class ClimbingStairs {
  20.     /**
  21.      * 这道题可以使用动态规划来解决。我们定义一个数组 dp，其中 dp[i] 表示爬到第 i 阶楼梯的不同方式的数量。
  22.      * 根据题目要求，爬到第 i 阶楼梯的方式只有两种：
  23.      * 1. 从第 i-1 阶楼梯爬一步到达：dp[i-1]
  24.      * 2. 从第 i-2 阶楼梯爬两步到达：dp[i-2]
  25.      * 所以，dp[i] = dp[i-1] + dp[i-2]，即爬到第 i 阶楼梯的不同方式数量等于爬到第 i-1 阶和第 i-2 阶楼梯方式数量之和。
  26.      * 初始条件是 dp[0] = 1（表示不爬任何台阶）和 dp[1] = 1（表示爬一阶台阶）。
  27.      * 最终要求的答案是 dp[n]，其中 n 表示楼梯的总阶数。
  28.      */
  29.     public int climbStairs(int n) {
  30.         if (n <= 1) {
  31.             return 1;
  32.         }
  33.  
  34.         // 创建一个数组来保存每个楼梯阶数对应的不同爬法数量
  35.         int[] dp = new int[n + 1];
  36.  
  37.         // 初始条件：第0阶和第1阶都只有一种爬法
  38.         dp[0] = 1;
  39.         dp[1] = 1;
  40.  
  41.         // 通过动态规划计算每个楼梯阶数对应的不同爬法数量
  42.         for (int i = 2; i <= n; i++) {
  43.             dp[i] = dp[i - 1] + dp[i - 2];
  44.         }
  45.  
  46.         // 返回爬到第n阶楼梯的不同爬法数量作为结果
  47.         return dp[n];
  48.     }
  49.  
  50.     public static void main(String[] args) {
  51.         System.out.println("楼顶数为2" + "，你到达楼顶的不同方式的数量为" + new ClimbingStairs().climbStairs(2));
  52.         System.out.println("楼顶数为3" + "，你到达楼顶的不同方式的数量为" + new ClimbingStairs().climbStairs(3));
  53.         System.out.println("楼顶数为4" + "，你到达楼顶的不同方式的数量为" + new ClimbingStairs().climbStairs(4));
  54.         System.out.println("楼顶数为5" + "，你到达楼顶的不同方式的数量为" + new ClimbingStairs().climbStairs(5));
  55.         System.out.println("楼顶数为6" + "，你到达楼顶的不同方式的数量为" + new ClimbingStairs().climbStairs(6));
  56.         System.out.println("楼顶数为34" + "，你到达楼顶的不同方式的数量为" + new ClimbingStairs().climbStairs(34));
  57.     }
  58. }

（十六）打家劫舍（House Robber）

题目描述:你是一个专业的小偷，计划偷窃一条街道上的房屋。每间房屋都存放着特定金额的财物，但相邻的房屋装有相互连通的防盗系统，如果同时选中了相邻的两间房屋进行偷窃，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，你需要计算在不触发警报的情况下，能够偷窃到的最高金额。

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

解释: 偷窃第1间和第3间房屋，金额总计为 1 + 3 = 4。

示例 2:输入: [2,7,9,3,1]   输出: 12

解释: 偷窃第1间、第3间和第5间房屋，金额总计为 2 + 9 + 1 = 12。

来源：力扣（LeetCode）

链接：力扣

解题思路

这道题可以使用动态规划来解决。我们定义一个数组 dp，其中 dp[i] 表示偷窃到第 i 间房屋时能够获得的最高金额。根据题目要求，我们不能选择相邻的房屋进行偷窃，因此对于第 i 间房屋，我们有两种选择：

  1. 偷窃第 i 间房屋：那么最高金额为 dp[i-2] + nums[i]，即第 i-2 间房屋的最高金额加上当前房屋的金额。
  2. 不偷窃第 i 间房屋：那么最高金额为 dp[i-1]，即前一间房屋的最高金额。

综上，我们可以得到状态转移方程：

dp[i] = max(dp[i-2] + nums[i], dp[i-1])

初始条件是 dp[0] = nums[0] 和 dp[1] = max(nums[0], nums[1])。

最终要求的答案是 dp[n-1]，其中 n 是房屋的数量。

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是房屋的数量。通过动态规划的思想，我们可以高效地计算出能够偷窃到的最高金额。

代码展示

下面是使用动态规划解决打家劫舍问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 你是一个专业的小偷，计划偷窃一条街道上的房屋。
  6.  * 每间房屋都存放着特定金额的财物，但相邻的房屋装有相互连通的防盗系统，
  7.  * 如果同时选中了相邻的两间房屋进行偷窃，系统会自动报警。
  8.  * 给定一个代表每个房屋存放金额的非负整数数组，你需要计算在不触发警报的情况下，能够偷窃到的最高金额。
  9.  * 示例 1:输入: [1,2,3,1]   输出: 4
  10.  * 解释: 偷窃第1间和第3间房屋，金额总计为 1 + 3 = 4。
  11.  * 示例 2:输入: [2,7,9,3,1]   输出: 12
  12.  * 解释: 偷窃第1间、第3间和第5间房屋，金额总计为 2 + 9 + 1 = 12。
  13.  * @date 2023/5/27  23:17
  14.  */
  15. public class HouseRobber {
  16.     /**
  17.      * 这道题可以使用动态规划来解决。
  18.      * 我们定义一个数组 dp，其中 dp[i] 表示偷窃到第 i 间房屋时能够获得的最高金额。
  19.      * 根据题目要求，我们不能选择相邻的房屋进行偷窃，因此对于第 i 间房屋，我们有两种选择：
  20.      * 1. 偷窃第 i 间房屋：那么最高金额为 dp[i-2] + nums[i]，即第 i-2 间房屋的最高金额加上当前房屋的金额。
  21.      * 2. 不偷窃第 i 间房屋：那么最高金额为 dp[i-1]，即前一间房屋的最高金额。
  22.      * 综上，我们可以得到状态转移方程：
  23.      * dp[i] = max(dp[i-2] + nums[i], dp[i-1])
  24.      * 初始条件是 dp[0] = nums[0] 和 dp[1] = max(nums[0], nums[1])。
  25.      * 最终要求的答案是 dp[n-1]，其中 n 是房屋的数量。
  26.      * 
  27.      * 该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是房屋的数量。
  28.      * 通过动态规划的思想，我们可以高效地计算出能够偷窃到的最高金额。
  29.      */
  30.     public int rob(int[] nums) {
  31.         if (nums == null || nums.length == 0) {
  32.             return 0;
  33.         }
  34.  
  35.         int n = nums.length;
  36.         if (n == 1) {
  37.             return nums[0];
  38.         }
  39.  
  40.         // 创建一个数组来保存偷窃到每个房屋时能够获得的最高金额
  41.         int[] dp = new int[n];
  42.  
  43.         // 初始条件：只有一间房屋时，能够偷窃的最高金额为该房屋的金额
  44.         dp[0] = nums[0];
  45.  
  46.         // 当有两间房屋时，偷窃其中金额较大的房屋
  47.         dp[1] = Math.max(nums[0], nums[1]);
  48.  
  49.         // 通过动态规划计算每个房屋对应的最高金额
  50.         for (int i = 2; i < n; i++) {
  51.             // 在偷窃第 i 间房屋时，有两种选择：偷窃第 i-2 间房屋+当前房屋金额 或 不偷窃第 i-1 间房屋，取较大值
  52.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  53.         }
  54.  
  55.         // 返回偷窃到最后一间房屋时能够获得的最高金额
  56.         return dp[n - 1];
  57.     }
  58.  
  59.     public static void main(String[] args) {
  60.         int[] nums1 = new int[]{1, 2, 3, 1};
  61.         System.out.println(new HouseRobber().rob(nums1));
  62.  
  63.         int[] nums2 = new int[]{2, 7, 9, 3, 1};
  64.         System.out.println(new HouseRobber().rob(nums2));
  65.     }
  66. }

（十七）强盗抢劫环形街区（House Robber II）

题目描述:你是一个专业的强盗，计划抢劫街区的房屋。每个房屋都存放着特定金额的钱。你面临的唯一约束条件是，由于安全系统的存在，相邻的房屋装有连接的警报系统。换句话说，如果两个相邻的房屋在同一晚上被打劫，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报系统的情况下，能够抢劫到的最高金额。

注意：这是一个环形街区，意味着第一个房屋和最后一个房屋是相邻的。

示例 1:输入: [2,3,2].  输出: 3

解释: 你可以选择从第一间房屋抢劫 2 元，然后跳过第二间房屋，接着抢劫第三间房屋 1 元。因此，抢劫到的最高金额为 3 元。

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

解释: 你可以选择抢劫第一间房屋 1 元和第三间房屋 3 元，抢劫到的最高金额为 4 元。注意，你不能选择抢劫第一间房屋和最后一间房屋，因为它们是相邻的。

来源：力扣（LeetCode）

链接：力扣

解题思路

解决强盗抢劫环形街区问题可以采用动态规划的思路。由于首尾房屋相邻，因此最后一间房屋只能选择抢劫或不抢劫。这样，原问题可以分解为两个子问题：

  1. 不抢劫最后一间房屋，即考虑抢劫第一间房屋到倒数第二间房屋的情况。
  2. 不抢劫第一间房屋，即考虑抢劫第二间房屋到最后一间房屋的情况。

对于这两个子问题，可以使用类似于"打家劫舍"问题的动态规划方法来求解。

具体步骤如下：

  1. 对于子问题1，创建一个动态规划数组 dp1，其中 dp1[i] 表示从第一间房屋到第 i 间房屋（不包括最后一间房屋）能够抢劫到的最高金额。初始化 dp1[0] = nums[0]，dp1[1] = max(nums[0], nums[1])。
  2. 对于子问题2，创建一个动态规划数组 dp2，其中 dp2[i] 表示从第二间房屋到第 i 间房屋能够抢劫到的最高金额。初始化 dp2[0] = 0，dp2[1] = nums[1]。
  3. 对于子问题1，从第三间房屋开始遍历，计算每个位置的最高金额：dp1[i] = max(dp1[i-2] + nums[i], dp1[i-1])。
  4. 对于子问题2，从第三间房屋开始遍历，计算每个位置的最高金额：dp2[i] = max(dp2[i-2] + nums[i+1], dp2[i-1])。
  5. 最后的结果为 max(dp1[n-2], dp2[n-1])，其中 n 为房屋数量。

代码展示

下面是使用动态规划解决强盗抢劫环形街区问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 你是一个专业的强盗，计划抢劫街区的房屋。每个房屋都存放着特定金额的钱。
  6.  * 你面临的唯一约束条件是，由于安全系统的存在，相邻的房屋装有连接的警报系统。
  7.  * 换句话说，如果两个相邻的房屋在同一晚上被打劫，系统会自动报警。
  8.  * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报系统的情况下，能够抢劫到的最高金额。
  9.  * 注意：这是一个环形街区，意味着第一个房屋和最后一个房屋是相邻的。
  10.  * 示例 1:输入: [2,3,2].  输出: 3
  11.  * 解释: 你可以选择从第一间房屋抢劫 2 元，然后跳过第二间房屋，接着抢劫第三间房屋 1 元。因此，抢劫到的最高金额为 3 元。
  12.  * 示例 2:输入: [1,2,3,1]  输出: 4
  13.  * 解释: 你可以选择抢劫第一间房屋 1 元和第三间房屋 3 元，抢劫到的最高金额为 4 元。
  14.  * 注意，你不能选择抢劫第一间房屋和最后一间房屋，因为它们是相邻的。
  15.  * @date 2023/5/27  23:25
  16.  */
  17. public class HouseRobberII {
  18.     /**
  19.      * 对于这两个子问题，可以使用类似于"打家劫舍"问题的动态规划方法来求解。
  20.      * 具体步骤如下：
  21.      * 1. 对于子问题1，创建一个动态规划数组 dp1，其中 dp1[i] 表示从第一间房屋到第 i 间房屋（不包括最后一间房屋）能够抢劫到的最高金额。
  22.      * 初始化 dp1[0] = nums[0]，dp1[1] = max(nums[0], nums[1])。
  23.      * 2. 对于子问题2，创建一个动态规划数组 dp2，其中 dp2[i] 表示从第二间房屋到第 i 间房屋能够抢劫到的最高金额。
  24.      * 初始化 dp2[0] = 0，dp2[1] = nums[1]。
  25.      * 3. 对于子问题1，从第三间房屋开始遍历，计算每个位置的最高金额：dp1[i] = max(dp1[i-2] + nums[i], dp1[i-1])。
  26.      * 4. 对于子问题2，从第三间房屋开始遍历，计算每个位置的最高金额：dp2[i] = max(dp2[i-2] + nums[i+1], dp2[i-1])。
  27.      * 5. 最后的结果为 max(dp1[n-2], dp2[n-1])，其中 n 为房屋数量。
  28.      */
  29.     public int rob(int[] nums) {
  30.         int n = nums.length;
  31.         if (n == 1) {
  32.             return nums[0];
  33.         }
  34.  
  35.         // 分为两个子问题：不抢劫最后一间房屋和不抢劫第一间房屋
  36.         int max1 = robHelper(nums, 0, n - 2);
  37.         int max2 = robHelper(nums, 1, n - 1);
  38.  
  39.         // 返回两个子问题的较大值
  40.         return Math.max(max1, max2);
  41.     }
  42.  
  43.     // 求解单个子问题的最大金额
  44.     private int robHelper(int[] nums, int start, int end) {
  45.         int n = end - start + 1;
  46.         if (n == 0) {
  47.             return 0;
  48.         }
  49.         if (n == 1) {
  50.             return nums[start];
  51.         }
  52.  
  53.         int[] dp = new int[n];
  54.         dp[0] = nums[start];
  55.         dp[1] = Math.max(nums[start], nums[start + 1]);
  56.  
  57.         for (int i = 2; i < n; i++) {
  58.             dp[i] = Math.max(dp[i - 2] + nums[start + i], dp[i - 1]);
  59.         }
  60.  
  61.         return dp[n - 1];
  62.     }
  63.  
  64.     public static void main(String[] args) {
  65.         int[] nums1 = {2, 3, 2};
  66.         int maxAmount1 = new HouseRobberII().rob(nums1);
  67.         // 输出：最大金额为：3
  68.         System.out.println("最大金额为：" + maxAmount1);
  69.  
  70.         int[] nums2 = {1, 2, 3, 1};
  71.         int maxAmount2 = new HouseRobberII().rob(nums2);
  72.         // 输出：最大金额为：4
  73.         System.out.println("最大金额为：" + maxAmount2);
  74.  
  75.         int[] nums3 = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
  76.         int maxAmount3 = new HouseRobberII().rob(nums3);
  77.         // 输出：最大金额为：16
  78.         System.out.println("最大金额为：" + maxAmount3);
  79.     }
  80.  
  81. }

（十八）股票买卖问题（Best Time to Buy and Sell Stock）

题目描述:给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

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

注意：你不能在买入股票前卖出股票。

示例 1:输入: prices = [7,1,5,3,6,4]. 输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:输入: prices = [7,6,4,3,1]  输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）

链接：力扣

解题思路

这道题可以使用动态规划来解决。

  • 我们可以定义两个变量 minPrice 和 maxProfit，分别表示当前遍历过的最低价格和当前的最大利润。
  • 在遍历股票价格数组时，我们可以更新 minPrice 为当前价格和 minPrice 中的较小值。然后，我们可以计算当前价格与 minPrice 的差值，并将其与 maxProfit 进行比较，更新 maxProfit 为较大值。
  • 最终，maxProfit 即为所能获取的最大利润。

该算法的时间复杂度为 O(n)，其中 n 是股票价格数组的长度。通过动态规划的思想，我们可以在一次遍历中找到最低价格和最大利润，从而解决股票买卖问题。

代码展示

下面是使用动态规划解决股票买卖问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
  6.  * 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
  7.  * 注意：你不能在买入股票前卖出股票。
  8.  * 示例 1:输入: prices = [7,1,5,3,6,4]. 输出: 5
  9.  * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。
  10.  * 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
  11.  * 示例 2:输入: prices = [7,6,4,3,1]  输出: 0
  12.  * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  13.  * @date 2023/5/28  23:31
  14.  */
  15. public class BestTimeBuyAndSellStock {
  16.     /**
  17.      * 这道题可以使用动态规划来解决。
  18.      * 我们可以定义两个变量 minPrice 和 maxProfit，分别表示当前遍历过的最低价格和当前的最大利润。
  19.      * 在遍历股票价格数组时，我们可以更新 minPrice 为当前价格和 minPrice 中的较小值。
  20.      * 然后，我们可以计算当前价格与 minPrice 的差值，并将其与 maxProfit 进行比较，更新 maxProfit 为较大值。
  21.      * 最终，maxProfit 即为所能获取的最大利润。
  22.      * 
  23.      * 该算法的时间复杂度为 O(n)，其中 n 是股票价格数组的长度。
  24.      * 通过动态规划的思想，我们可以在一次遍历中找到最低价格和最大利润，从而解决股票买卖问题。
  25.      */
  26.     public int maxProfit(int[] prices) {
  27.         // 初始化最低价格为正无穷大
  28.         int minPrice = Integer.MAX_VALUE;
  29.         // 初始化最大利润为0
  30.         int maxProfit = 0;
  31.  
  32.         for (int i = 0; i < prices.length; i++) {
  33.             if (prices[i] < minPrice) {
  34.                 minPrice = prices[i];
  35.             } else if (prices[i] - minPrice > maxProfit) {
  36.                 maxProfit = prices[i] - minPrice;
  37.             }
  38.         }
  39.  
  40.         return maxProfit;
  41.     }
  42.  
  43.     public static void main(String[] args) {
  44.         int[] prices1 = {7, 1, 5, 3, 6, 4};
  45.         int maxProfit1 = new BestTimeBuyAndSellStock().maxProfit(prices1);
  46.         // 输出：最大利润：5
  47.         System.out.println("最大利润：" + maxProfit1);
  48.  
  49.         int[] prices2 = {7, 6, 4, 3, 1};
  50.         int maxProfit2 = new BestTimeBuyAndSellStock().maxProfit(prices2);
  51.         // 输出：最大利润：0
  52.         System.out.println("最大利润：" + maxProfit2);
  53.     }
  54. }

（十九）最佳买卖股票时机含冷冻期（Best Time to Buy and Sell Stock with Cooldown）

题目描述:给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

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

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

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

解释: 在第 2 天（股票价格 = 2）的时候买入，在第 3 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-2 = 1 。

 随后，在第 4 天（股票价格 = 0）的时候买入，在第 5 天（股票价格 = 2）的时候卖出，这笔交易所能获得利润 = 2-0 = 2 。

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法采用动态规划来解决含有冷冻期的买卖股票问题。

假设有三个状态：

  1. hold[i]：表示第 i 天持有股票时的最大利润。
  2. notHold[i]：表示第 i 天不持有股票时的最大利润。
  3. cooldown[i]：表示第 i 天处于冷冻期时的最大利润。

对于第 i 天的状态转移，可以根据前一天的状态计算得出：

  • 如果第 i 天持有股票，则可能是前一天已经持有股票，或者是前一天不持有股票但在冷冻期之前买入股票。
  • 如果第 i 天不持有股票，则可能是前一天已经不持有股票，或者是前一天在冷冻期之前卖出了股票。
  • 如果第 i 天处于冷冻期，则前一天必须卖出股票。

具体状态转移方程如下：

  1. hold[i] = max(hold[i-1], notHold[i-1] - prices[i])
  2. notHold[i] = max(notHold[i-1], cooldown[i-1])
  3. cooldown[i] = hold[i-1] + prices[i]

最终的答案是 max(notHold[n-1], cooldown[n-1])，其中 n 是数组 prices 的长度。

代码展示

下面是使用动态规划解决含有冷冻期的买卖股票问题的代码示例：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。
  6.  * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
  7.  * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  8.  * 示例 1:输入: [1,2,3,0,2]  输出: 3
  9.  * 解释: 在第 2 天（股票价格 = 2）的时候买入，在第 3 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-2 = 1 。
  10.  * 随后，在第 4 天（股票价格 = 0）的时候买入，在第 5 天（股票价格 = 2）的时候卖出，这笔交易所能获得利润 = 2-0 = 2 。
  11.  * @date 2023/5/29  23:37
  12.  */
  13. public class BestTimeBuyAndSellStockWithCooldown {
  14.     /**
  15.      * 最优解法采用动态规划来解决含有冷冻期的买卖股票问题。
  16.      * 假设有三个状态：
  17.      * 1. hold[i]：表示第 i 天持有股票时的最大利润。
  18.      * 2. notHold[i]：表示第 i 天不持有股票时的最大利润。
  19.      * 3. cooldown[i]：表示第 i 天处于冷冻期时的最大利润。
  20.      * 对于第 i 天的状态转移，可以根据前一天的状态计算得出：
  21.      * * 如果第 i 天持有股票，则可能是前一天已经持有股票，或者是前一天不持有股票但在冷冻期之前买入股票。
  22.      * * 如果第 i 天不持有股票，则可能是前一天已经不持有股票，或者是前一天在冷冻期之前卖出了股票。
  23.      * * 如果第 i 天处于冷冻期，则前一天必须卖出股票。
  24.      * 具体状态转移方程如下：
  25.      * hold[i] = max(hold[i-1], notHold[i-1] - prices[i])
  26.      * notHold[i] = max(notHold[i-1], cooldown[i-1])
  27.      * cooldown[i] = hold[i-1] + prices[i]
  28.      * 最终的答案是 max(notHold[n-1], cooldown[n-1])，其中 n 是数组 prices 的长度。
  29.      */
  30.     public int maxProfit(int[] prices) {
  31.         if (prices == null || prices.length <= 1) {
  32.             return 0;
  33.         }
  34.  
  35.         int n = prices.length;
  36.         int[] hold = new int[n];
  37.         int[] notHold = new int[n];
  38.         int[] cooldown = new int[n];
  39.  
  40.         hold[0] = -prices[0];
  41.  
  42.         for (int i = 1; i < n; i++) {
  43.             hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i]);
  44.             notHold[i] = Math.max(notHold[i - 1], cooldown[i - 1]);
  45.             cooldown[i] = hold[i - 1] + prices[i];
  46.         }
  47.  
  48.         return Math.max(notHold[n - 1], cooldown[n - 1]);
  49.     }
  50.  
  51.     public static void main(String[] args) {
  52.         int[] prices1 = {1, 2, 3, 0, 2};
  53.         int maxProfit1 = new BestTimeBuyAndSellStockWithCooldown().maxProfit(prices1);
  54.         // 输出：最大利润为：3
  55.         System.out.println("最大利润为：" + maxProfit1);
  56.  
  57.         int[] prices2 = {7, 1, 5, 3, 6, 4};
  58.         int maxProfit2 = new BestTimeBuyAndSellStockWithCooldown().maxProfit(prices2);
  59.         // 输出：最大利润为：5
  60.         System.out.println("最大利润为：" + maxProfit2);
  61.  
  62.         int[] prices3 = {1, 2, 3, 4, 5};
  63.         int maxProfit3 = new BestTimeBuyAndSellStockWithCooldown().maxProfit(prices3);
  64.         // 输出：最大利润为：4
  65.         System.out.println("最大利润为：" + maxProfit3);
  66.  
  67.         int[] prices4 = {7, 6, 4, 3, 1};
  68.         int maxProfit4 = new BestTimeBuyAndSellStockWithCooldown().maxProfit(prices4);
  69.         // 输出：最大利润为：0
  70.         System.out.println("最大利润为：" + maxProfit4);
  71.     }
  72. }

（二十）找零钱的最少硬币数（Coin Change）

题目描述:给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

示例 1:输入: coins = [1, 2, 5], amount = 11.      输出: 3

解释: 11 = 5 + 5 + 1

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

来源：力扣（LeetCode）

链接：力扣

解题思路

该问题可以使用动态规划来解决。

  • 我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。
  • 初始化数组 dp 为无穷大，除了 dp[0] = 0，表示凑成金额为 0 不需要任何硬币。
  • 接下来，我们遍历金额从 1 到 amount，对于每个金额 i，我们枚举所有的硬币面额 coin，如果 coin 小于等于 i，则说明可以使用该硬币，更新 dp[i] 的值为 dp[i - coin] + 1 和当前 dp[i] 的较小值。
  • 最终，dp[amount] 就是凑成总金额所需的最少硬币个数。

代码展示

下面是使用动态规划解决找零钱的最少硬币数问题的代码示例（使用Java）：

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author yanfengzhang
  7.  * @description 给定不同面额的硬币 coins 和一个总金额 amount，
  8.  * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
  9.  * 你可以认为每种硬币的数量是无限的。
  10.  * 示例 1:输入: coins = [1, 2, 5], amount = 11.      输出: 3
  11.  * 解释: 11 = 5 + 5 + 1
  12.  * 示例 2:输入: coins = [2], amount = 3      输出: -1
  13.  * @date 2023/5/26  23:41
  14.  */
  15. public class CoinChange {
  16.     /**
  17.      * 我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。
  18.      * 初始化数组 dp 为无穷大，除了 dp[0] = 0，表示凑成金额为 0 不需要任何硬币。
  19.      * 接下来，我们遍历金额从 1 到 amount，对于每个金额 i，
  20.      * 我们枚举所有的硬币面额 coin，如果 coin 小于等于 i，则说明可以使用该硬币，
  21.      * 更新 dp[i] 的值为 dp[i - coin] + 1 和当前 dp[i] 的较小值。
  22.      * 最终，dp[amount] 就是凑成总金额所需的最少硬币个数。
  23.      */
  24.     public int coinChange(int[] coins, int amount) {
  25.         int[] dp = new int[amount + 1];
  26.         Arrays.fill(dp, Integer.MAX_VALUE);
  27.         dp[0] = 0;
  28.  
  29.         for (int i = 1; i <= amount; i++) {
  30.             for (int coin : coins) {
  31.                 if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
  32.                     dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  33.                 }
  34.             }
  35.         }
  36.  
  37.         return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
  38.     }
  39.  
  40.     public static void main(String[] args) {
  41.         int[] coins1 = {1, 2, 5};
  42.         int amount1 = 11;
  43.         int minCoins1 = new CoinChange().coinChange(coins1, amount1);
  44.         System.out.println("凑成总金额 " + amount1 + " 所需的最少硬币个数为：" + minCoins1);
  45.  
  46.         int[] coins2 = {2};
  47.         int amount2 = 3;
  48.         int minCoins2 = new CoinChange().coinChange(coins2, amount2);
  49.         System.out.println("凑成总金额 " + amount2 + " 所需的最少硬币个数为：" + minCoins2);
  50.     }
  51. }

（二十一）从起点到终点的最小路径数（Unique Paths）

题目描述：给定一个二维网格，大小为 m x n，网格中的每个格子都代表一个空地。起始点位于左上角，即网格的左上角格子，终点位于右下角，即网格的右下角格子。在每个格子中，你只能向下或向右移动。请计算从起始点到终点的不同路径的数目。

例如，给定一个 3 x 3 的网格，起始点为左上角格子 (0, 0)，终点为右下角格子 (2, 2)。在这个网格中，总共有 3 条不同的路径。

1  1  1

1  1  1

1  1  1

提示：每次只能向下或向右移动一步。

来源：力扣（LeetCode）

链接：力扣

解法分析

最优解法是使用动态规划来解决该问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从起始点到达格子 (i, j) 的不同路径数目。

具体步骤如下：

  1. 初始化边界条件：将 dp[0][j] 和 dp[i][0]（即第一行和第一列）的值都设置为 1，因为只能向下或向右移动，所以第一行和第一列的格子只有一种路径到达。
  2. 遍历网格的每个格子，计算不同路径数目：对于格子 (i, j)，可以从上方的格子 (i-1, j) 或左侧的格子 (i, j-1) 到达。因此，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
  3. 最后返回 dp[m-1][n-1]，即终点的不同路径数目。

该算法的时间复杂度是 O(m * n)，其中 m 和 n 分别是网格的行数和列数，因为需要遍历所有格子。空间复杂度是 O(m * n)，需要使用一个二维数组来存储中间结果。

代码展示

  1. package org.zyf.javabasic.letcode.dynamicprogramming;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或向右移动一步。
  6.  * 机器人试图达到网格的右下角。问总共有多少条不同的路径？
  7.  * 例如，一个 3 x 7 的网格，机器人从左上角到右下角总共有 28 条不同的路径。
  8.  * 注意：m 和 n 的值均不超过 100。
  9.  * 示例 1:输入: m = 3, n = 2.       输出: 3
  10.  * 解释: 从左上角开始，总共有三条路径可以到达右下角。
  11.  * 1. 向右 -> 向右 -> 向下
  12.  * 2. 向右 -> 向下 -> 向右
  13.  * 3. 向下 -> 向右 -> 向右
  14.  * 示例 2:输入: m = 7, n = 3       输出: 28
  15.  * @date 2023/5/12  23:24
  16.  */
  17. public class UniquePaths {
  18.     /**
  19.      * 这道题可以使用动态规划来解决。
  20.      * 我们定义一个二维数组 dp，其中 dp[i][j] 表示从起始位置到达网格 (i, j) 的不同路径数。
  21.      * 根据题目要求，机器人每次只能向下或向右移动，
  22.      * 因此对于网格中的每个位置 (i, j)，可以从上方的位置 (i-1, j) 或左方的位置 (i, j-1) 到达。
  23.      * 
  24.      * 根据上述分析，可以得到状态转移方程：
  25.      * dp[i][j] = dp[i-1][j] + dp[i][j-1]
  26.      * 初始条件为：当 i=0 或 j=0 时，只有一条路径可以到达，因此 dp[i][j] = 1。
  27.      * 最终要求的答案是 dp[m-1][n-1]，其中 m 和 n 分别是网格的行数和列数。
  28.      * 
  29.      * 该算法的时间复杂度为 O(m * n)，空间复杂度为 O(m * n)，其中 m 和 n 分别是网格的行数和列数。
  30.      * 通过动态规划的思想，我们可以高效地计算出不同路径的数量。
  31.      */
  32.     public int uniquePaths(int m, int n) {
  33.         int[][] dp = new int[m][n];
  34.  
  35.         // 初始化第一行和第一列的路径数为1
  36.         for (int i = 0; i < m; i++) {
  37.             dp[i][0] = 1;
  38.         }
  39.         for (int j = 0; j < n; j++) {
  40.             dp[0][j] = 1;
  41.         }
  42.  
  43.         // 计算其他位置的路径数
  44.         for (int i = 1; i < m; i++) {
  45.             for (int j = 1; j < n; j++) {
  46.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  47.             }
  48.         }
  49.  
  50.         return dp[m - 1][n - 1];
  51.     }
  52.  
  53.     public static void main(String[] args) {
  54.         int m1 = 3, n1 = 2;
  55.         int paths1 = new UniquePaths().uniquePaths(m1, n1);
  56.         // 输出：不同路径的数量：3
  57.         System.out.println("不同路径的数量：" + paths1);
  58.  
  59.         int m2 = 7, n2 = 3;
  60.         int paths2 = new UniquePaths().uniquePaths(m2, n2);
  61.         // 输出：不同路径的数量：28
  62.         System.out.println("不同路径的数量：" + paths2);
  63.     }
  64.  
  65. }

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览62532 人正在系统学习中
注：本文转载自blog.csdn.net的张彦峰ZYF的文章"https://blog.csdn.net/xiaofeng10330111/article/details/105640313"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！