动态规划之 多重背包 基础题
多重背包
理论基础
携带矿石资源
import java.util.*;
public class Main {
public static void main(String[] args) {
// 创建Scanner对象，用于从控制台读取输入
Scanner input = new Scanner(System.in);
// 读取背包的容量
int bagSize = input.nextInt();
// 读取物品的种类数量
int kinds = input.nextInt();
// 创建一个数组来存储每种物品的重量，数组大小为种类数加1（因为数组下标从1开始）
int weight[] = new int[kinds + 1];
// 循环读取每种物品的重量
for (int i = 1; i <= kinds; i++) {
weight[i] = input.nextInt();
}
// 创建一个数组来存储每种物品的价格，数组大小和重量数组相同
int prices[] = new int[kinds + 1];
// 循环读取每种物品的价格
for (int i = 1; i <= kinds; i++) {
prices[i] = input.nextInt();
}
// 创建一个数组来存储每种物品可以使用的最大数量，数组大小和重量数组相同
int canUseNums[] = new int[kinds + 1];
// 循环读取每种物品可以使用的最大数量
for (int i = 1; i <= kinds; i++) {
canUseNums[i] = input.nextInt();
}
// 创建一个动态规划数组dp，大小为背包容量加1，用于存储每个容量下的最大价值
int dp[] = new int[bagSize + 1];
// 外层循环遍历每种物品
for (int i = 1; i <= kinds; i++) {
// 内层循环从背包容量开始向下遍历，确保不会超过背包容量
for (int j = bagSize; j >= weight[i]; j--) {
// 最内层循环遍历当前物品可以使用的数量，从1到最大可用数量
for (int k = 1; k <= canUseNums[i] && (j - k * weight[i]) >= 0; k++) {
// 更新dp数组，计算当前容量下的最大价值
dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * prices[i]);
}
}
}
// 输出背包容量下的最大价值
System.out.println(dp[bagSize]);
}
}基础题
打家劫舍
class Solution {
/**
* 计算在不触动相邻房屋报警系统的情况下，能够抢劫到的最大金额。
*
* @param nums 代表每个房子中存放的金额的数组
* @return 返回能够抢劫到的最大金额
*/
public int rob(int[] nums) {
// 如果数组为空或者为null，返回0，因为没有房子可以抢劫
if (nums == null || nums.length == 0) {
return 0;
}
// 获取数组的长度
int len = nums.length;
// 如果只有一个房子，直接返回该房子的金额
if (len == 1) {
return nums[0];
}
// 初始化动态规划数组，长度与输入数组相同
int[] dp = new int[len];
// 第一个房子的抢劫金额为该房子的金额
dp[0] = nums[0];
// 第二个房子的抢劫金额为第一个和第二个房子金额的最大值
dp[1] = Math.max(nums[0], nums[1]);
// 从第三个房子开始遍历，使用动态规划求解
for (int i = 2; i < len; i++) {
// 对于每个房子，有两种选择：抢或不抢
// 如果选择抢，那么不能抢前一个房子，所以取dp[i - 2]的值加上当前房子的金额
// 如果选择不抢，那么取dp[i - 1]的值
// 取这两种选择中的最大值作为dp[i]的值
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
// 返回最后一个房子的抢劫金额，即最大抢劫金额
return dp[len - 1];
}
}打家劫舍II
class Solution {
// 定义一个数组用于存储每个房子的最大抢劫金额
int dp[];
// 记录房子的数量
int len;
public int rob(int[] nums) {
// 如果数组为空或者没有房子，则返回0
if (nums == null || nums.length == 0) {
return 0;
}
// 获取房子的数量
len = nums.length;
// 初始化dp数组，长度为房子的数量
dp = new int[len];
// 如果只有一套房子，则盗贼只能选择打劫或不打劫这一套，返回该房子的金额
if (len == 1) {
return nums[0];
}
// 调用Demo方法，分别计算不打劫第一套房子和打劫第一套房子的情况下的最大金额
// 并将两者的最大值返回
return Math.max(Demo(nums, 0, len - 2), Demo(nums, 1, len - 1));
}
// Demo方法用于计算从start到end房子的最大抢劫金额
int Demo(int nums[], int start, int end) {
// 如果只有一套房子，则返回该房子的金额
if (len == start + 1) {
return nums[start];
}
// 初始化前两套房子的最大抢劫金额
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start + 1]);
// 从第三套房子开始，遍历到end房子
for (int i = start + 2; i <= end; i++) {
// 对于每套房子，计算打劫当前房子和不打劫当前房子的最大金额，并取两者的最大值
// dp[i - 2] + nums[i]表示打劫当前房子的情况，因为不能连续打劫相邻的房子，所以上一个房子不能打劫
// dp[i - 1]表示不打劫当前房子的情况
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
// 返回最后计算的最大抢劫金额
return dp[end];
}
}打家劫舍 III
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 用于存储当前节点抢劫时的最大金额
HashMap<TreeNode, Integer> doRob;
// 用于存储当前节点不抢劫时的最大金额
HashMap<TreeNode, Integer> doNotRob;
public int rob(TreeNode root) {
// 如果树为空，返回0
if(root == null){
return 0;
}
// 初始化抢劫和不抢劫的HashMap
doRob = new HashMap<>();
doNotRob = new HashMap<>();
// 调用DFS函数
Demo(root);
// 获取根节点抢劫和不抢劫的最大金额，并返回两者中的最大值
int doRobRes = doRob.getOrDefault(root, 0);
int doNotRobRes = doNotRob.getOrDefault(root, 0);
return Math.max(doRobRes, doNotRobRes);
}
// DFS函数，用于计算每个节点抢劫和不抢劫的最大金额
void Demo(TreeNode node){
if(node == null){
// 如果节点为空，直接返回
return;
}
// 先递归处理左子树和右子树
Demo(node.left);
Demo(node.right);
// 计算当前节点抢劫时的最大金额
// 包括当前节点的值加上左右子树不抢劫时的最大金额
doRob.put(node,
node.val + doNotRob.getOrDefault(node.left, 0) + doNotRob.getOrDefault(node.right, 0)
);
// 计算当前节点不抢劫时的最大金额
// 包括左右子树抢劫和不抢劫的最大金额中的最大值
doNotRob.put(node,
Math.max(doNotRob.getOrDefault(node.left, 0), doRob.getOrDefault(node.left, 0)) +
Math.max(doNotRob.getOrDefault(node.right, 0), doRob.getOrDefault(node.right, 0))
);
}
}买卖股票的最佳时机
class Solution {
/**
* 计算给定股票价格数组中的最大利润。
*
* @param prices 股票价格数组，表示每天的股票价格。
* @return 最大利润，如果无法获得利润则返回0。
*/
public int maxProfit(int[] prices) {
// 初始化最小值和最大利润
int minValue = Integer.MAX_VALUE; // 用来记录迄今为止遇到的最小价格
int maxGet = 0; // 用来记录迄今为止的最大利润
// 遍历价格数组
for(int i = 0 ; i < prices.length; i++){
// 如果当前价格小于记录的最小值，则更新最小值
if(minValue > prices[i]){
minValue = prices[i];
}
// 计算当前价格与最小值之间的差值，如果这个差值大于记录的最大利润，则更新最大利润
if(prices[i] - minValue > maxGet){
maxGet = prices[i] - minValue;
}
}
// 返回计算出的最大利润
return maxGet;
}
}买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
class Solution {
public int maxProfit(int[] prices) {
// prices数组的长度
int n = prices.length;
// 创建一个二维数组dp，用于存储动态规划的状态
// dp[i][0]表示第i天手中有股票的最大利润
// dp[i][1]表示第i天手中无股票的最大利润
int dp[][] = new int[n][2];
// 初始化状态，第0天买入股票，所以利润为负的第0天股票价格
dp[0][0] = -prices[0];
// 遍历prices数组，从第1天开始
for(int i = 1; i < n; i++){
// 更新状态0，表示第i天手中有股票的最大利润
// 我们可以选择继续持有股票（dp[i - 1][0]），或者在第i天买入股票（dp[i - 1][1] - prices[i]）
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
// 更新状态1，表示第i天手中无股票的最大利润
// 我们可以选择继续无股票（dp[i - 1][1]），或者在第i天卖出股票（dp[i - 1][0] + prices[i]）
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
// 返回第n - 1天手中无股票的最大利润，因为我们要最大化利润，所以只关心卖股票的情况
return dp[n - 1][1];
}
}买卖股票的最佳时机III
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
class Solution {
// 计算给定股票价格数组的最大利润，允许最多两次交易
public int maxProfit(int[] prices) {
// prices数组的长度
int len = prices.length;
// 初始化变量
// buy1表示第一次买入的价格（负数，因为买入股票是花钱的）
// sell1表示第一次卖出的价格
int buy1 = -prices[0], sell1 = 0;
// buy2表示第二次买入的价格
// sell2表示第二次卖出的价格
int buy2 = -prices[0], sell2 = 0;
// 从第二个价格开始遍历数组
for(int i = 1; i < len; i++){
// 更新第一次买入的价格，取之前买入价格和当前价格的负值的最大值
// 因为买入价格越低越好，所以取两者中更小的一个
buy1 = Math.max(buy1, -prices[i]);
// 更新第一次卖出的价格，取之前卖出价格和当前价格加上之前买入价格的最大值
// 因为卖出价格越高越好，所以取两者中更大的一个
sell1 = Math.max(sell1, buy1 + prices[i]);
// 更新第二次买入的价格，取之前第二次买入价格和第一次卖出价格减去当前价格的最大值
// 因为买入价格越低越好，所以取两者中更小的一个
buy2 = Math.max(buy2, sell1 - prices[i]);
// 更新第二次卖出的价格，取之前第二次卖出价格和当前价格加上第二次买入价格的最大值
// 因为卖出价格越高越好，所以取两者中更大的一个
sell2 = Math.max(sell2, buy2 + prices[i]);
}
// 返回第二次卖出的最大利润
return sell2;
}
}买卖股票的最佳时机IV
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
class Solution {
public int maxProfit(int k, int[] prices) {
// 如果价格数组为空或长度为0，则没有利润，返回0
if(prices == null || prices.length == 0){
return 0;
}
// 初始化动态规划数组dp，其中dp[i][j]表示第i天结束时，进行过j次交易的最大利润
int dp[][] = new int[prices.length][2 * k + 1];
// 初始化第一天的价格，将所有奇数索引（代表持有股票）设置为负的第一天价格
// 这是因为我们不能在第一天卖出股票，所以持有股票的成本是负的价格
for(int j = 1; j < 2 * k ; j += 2){
dp[0][j] = -prices[0];
}
// 遍历每一天的价格
for(int i = 1 ; i < prices.length; i++){
// 遍历每一种交易次数
for(int j = 0 ; j < 2 * k - 1; j += 2){
// dp[i][j + 1]表示第i天结束时，进行过j次交易后卖出股票的最大利润
// 我们可以选择不卖（保持前一天的状态dp[i - 1][j + 1]）或者卖出（前一天持有股票dp[i - 1][j]减去当前天的价格）
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
// dp[i][j + 2]表示第i天结束时，进行过j+1次交易后买入股票的最大利润
// 我们可以选择不买（保持前一天的状态dp[i - 1][j + 2]）或者买入（前一天卖出股票dp[i - 1][j + 1]加上当前天的价格）
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
// 返回最后一天结束时，进行过k次交易的最大利润
return dp[prices.length - 1][2 * k];
}
}最佳买卖股票时机含冷冻期
309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
class Solution {
public int maxProfit(int[] prices) {
// prices数组的长度
int len = prices.length;
// 创建一个二维数组dp，用于存储动态规划的状态
// dp[i][j]表示第i天的第j种状态的最大利润
// 这里的状态有4种：
// 0 - 手中持有股票
// 1 - 保持卖出状态
// 2 - 今天卖
// 3 - 今天冷冻期
int dp[][] = new int[len][4];
// 初始化状态0，表示第0天手中没有股票，利润为负的第0天股票价格
// 因为我们可以在第0天买入股票，所以利润为-prices[0]
dp[0][0] = -prices[0];
// 遍历prices数组，从第1天开始
for(int i = 1; i < len; i++){
// 更新状态0，表示第i天手中持有股票
// 我们可以选择继续不持有股票（dp[i - 1][0]），或者在冷冻期买入股票（dp[i - 1][3] - prices[i]）
// 或者在保持卖出状态买入股票（dp[i - 1][1] - prices[i]）
dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
// 更新状态1，表示第i天保持卖出状态
// 我们可以选择继续保持卖出状态（dp[i - 1][1]），或者昨天冷冻期（dp[i - 1][0] + prices[i]）
dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1]);
// 更新状态2，表示第i天卖
// 昨天持有股票，今天卖
dp[i][2] = dp[i - 1][0] + prices[i];
// 更新状态3，表示第i天冷冻期
// 昨天卖了
dp[i][3] = dp[i - 1][2];
}
// 返回第len - 1天的最大利润，可以是保持卖出状态（dp[len - 1][1]），第i天卖（dp[len - 1][2]），或者今天卖（dp[len - 1][3]）
return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
}
}买卖股票的最佳时机含手续费
class Solution {
// 定义一个方法，计算给定价格数组和手续费下的最大利润
public int maxProfit(int[] prices, int fee) {
// 记录价格数组的长度
int n = prices.length;
// 创建一个二维数组dp，其中dp[i][0]表示第i天持有股票的最大利润，
// dp[i][1]表示第i天无股票的最大利润
int dp[][] = new int[n][2];
// 初始化dp[0][0]为-prices[0]，表示第0天买入了股票，所以利润为负的买入价格
dp[0][0] = -prices[0];
// 从第二天开始遍历价格数组
for(int i = 1; i < n ; i++){
// 更新dp[i][0]，表示第i天持有股票的最大利润
// 可以选择继续持有股票（即保持前一天持有股票的最大利润dp[i - 1][0]），
// 或者选择在今天买入股票（即前一天持无股票的最大利润dp[i - 1][1]减去今天的买入价格）
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
// 更新dp[i][1]，表示第i天无股票的最大利润
// 可以选择继续无股票（即保持前一天无股票的最大利润dp[i - 1][1]），
// 或者选择在今天卖出股票（即前一天持有股票的最大利润dp[i - 1][0]加上今天的买入价格减去手续费）
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
// 返回最后一天无股票的最大利润，即dp[n - 1][1]
return dp[n - 1][1];
}
}最长递增子序列
class Solution {
/**
* 计算最长递增子序列的长度。
*
* @param nums 输入的整数数组
* @return 最长递增子序列的长度
*/
public int lengthOfLIS(int[] nums) {
// 如果数组为空或为null，返回0
if(nums.length == 0 || nums == null){
return 0;
}
// 初始化动态规划数组dp，长度与输入数组相同
int dp[] = new int[nums.length];
// 初始化结果res为1，因为至少每个元素自身可以构成一个长度为1的递增子序列
int res = 1;
// 将dp数组填充为1，因为每个元素至少可以构成长度为1的递增子序列
Arrays.fill(dp, 1);
// 遍历数组，从第二个元素开始
for(int i = 1; i < nums.length; i++){
// 对于当前元素nums[i]，遍历其之前的所有元素
for(int j = 0 ; j < i; j++){
// 如果当前元素大于之前的元素，说明可以构成递增子序列
if(nums[i] > nums[j]){
// 更新dp[i]为max(dp[i], dp[j] + 1)，即当前元素能构成的最长递增子序列长度
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 更新结果res为max(res, dp[i])，即整个数组能构成的最长递增子序列长度
res = Math.max(res, dp[i]);
}
// 返回最长递增子序列的长度
return res;
}
}最长连续递增序列
这题和上题的区别就是连续与否
class Solution {
// 该方法用于找出给定数组中最长连续递增子序列的长度
public int findLengthOfLCIS(int[] nums) {
// 如果数组长度小于等于1，直接返回数组长度，因为单个元素或空数组本身就是一个连续递增子序列
if(nums.length <= 1){
return nums.length;
}
// 初始化结果变量res为0，用于存储最长连续递增子序列的长度
int res = 0;
// 创建一个与输入数组同样长度的数组dp，用于存储以每个位置结尾的最长连续递增子序列的长度
int dp[] = new int[nums.length];
// 将dp数组的所有元素初始化为1，因为每个元素至少可以构成长度为1的连续递增子序列
Arrays.fill(dp, 1);
// 从数组的第二个元素开始遍历
for(int i = 1 ; i < nums.length; i++){
// 如果当前元素大于前一个元素，说明当前元素与前一个元素构成连续递增子序列
if(nums[i] > nums[i - 1]){
// 更新dp[i]为dp[i-1]+1，即当前位置的最长连续递增子序列长度为前一个位置的最长连续递增子序列长度加1
dp[i] = dp[i - 1] + 1;
}
// 更新res为dp[i]和res中的最大值，即记录遍历过程中找到的最长连续递增子序列的长度
res = Math.max(dp[i], res);
}
// 返回res，即整个数组中最长连续递增子序列的长度
return res;
}
}最长重复子数组
就是求最长的重复的子序列，要连在一起的
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int dp[][] = new int[nums1.length + 1][nums2.length + 1];
int maxLength = 0; // 用于记录最长公共子数组的长度
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // 当元素相等时，公共子数组长度加1
maxLength = Math.max(maxLength, dp[i][j]); // 更新最大长度
} else {
dp[i][j] = 0; // 不相等时，公共子数组长度为0
}
}
}
return maxLength; // 返回最长公共子数组的长度
}
}
最长公共子序列
class Solution {
/**
* 计算两个字符串的最长公共子序列长度。
* @param text1 第一个字符串
* @param text2 第二个字符串
* @return 两个字符串的最长公共子序列长度
*/
public int longestCommonSubsequence(String text1, String text2) {
// 获取两个字符串的长度
int Len1 = text1.length();
int Len2 = text2.length();
// 将字符串转换为字符数组，便于通过索引访问
char text1CharArray[] = text1.toCharArray();
char text2CharArray[] = text2.toCharArray();
// 创建二维数组dp，用于存储动态规划的中间结果
// dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度
int dp[][] = new int[Len1 + 1][Len2 + 1];
int res = 0; // 用于存储最终结果，即最长公共子序列的长度
// 外层循环遍历text1的每个字符
for(int i = 1 ; i <= Len1; i++){
// 内层循环遍历text2的每个字符
for(int j = 1; j <= Len2; j++){
// 如果当前字符相同，则最长公共子序列长度加1
if(text1CharArray[i - 1] == text2CharArray[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]);
}
// 更新全局最长公共子序列长度
res = Math.max(dp[i][j], res);
}
}
// 返回最长公共子序列的长度
return res;
}
}不相交的线
最长公共子序列变种
class Solution {
/**
* 计算两个字符串的最长公共子序列（LCS）。
* @param text1 第一个字符串
* @param text2 第二个字符串
* @return 两个字符串的最长公共子序列的长度
*/
public int longestCommonSubsequence(String text1, String text2) {
// 获取两个字符串的长度
int len1 = text1.length();
int len2 = text2.length();
// 将字符串转换为字符数组，便于索引访问
char text1CharArr[] = text1.toCharArray();
char text2CharArr[] = text2.toCharArray();
// 创建一个二维数组dp，用于存储动态规划的结果
// dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度
int dp[][] = new int[len1 + 1][len2 + 1];
int res = 0; // 用于存储最终的最长公共子序列的长度
// 遍历两个字符串的每个字符
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 如果当前字符相同，则最长公共子序列的长度加1
if (text1CharArr[i - 1] == text2CharArr[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]);
}
// 更新最长公共子序列的长度
res = Math.max(res, dp[i][j]);
}
}
// 返回最长公共子序列的长度
return res;
}
}两个字符串的删除操作
最长公共子序列变种
583. 两个字符串的删除操作 - 力扣（LeetCode）
class Solution {
/**
* 计算将一个字符串转换成另一个字符串所需的最小操作次数。
* 操作包括插入、删除和替换字符。
* @param word1 第一个字符串
* @param word2 第二个字符串
* @return 将word1转换成word2所需的最小操作次数
*/
public int minDistance(String word1, String word2) {
// 获取两个字符串的长度
int len1 = word1.length();
int len2 = word2.length();
// 将字符串转换为字符数组，便于索引访问
char word1CharArr[] = word1.toCharArray();
char word2CharArr[] = word2.toCharArray();
// 创建一个二维数组dp，用于存储动态规划的结果
// dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最小操作次数
int dp[][] = new int[len1 + 1][len2 + 1];
int max = 0; // 用于存储最长公共子序列的长度
// 遍历两个字符串的每个字符
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 如果当前字符相同，则不需要额外操作，继承之前的最小操作次数
if (word1CharArr[i - 1] == word2CharArr[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 如果当前字符不同，则考虑插入、删除和替换操作
// 取插入、删除和替换操作中的最小值加1
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
// 更新最长公共子序列的长度
max = Math.max(dp[i][j], max);
}
}
// 计算最小编辑距离，即两个字符串长度之和减去最长公共子序列长度的两倍
// 因为最长公共子序列的每个字符不需要操作，所以需要从总操作次数中减去
return (len1 + len2) - max * 2;
}
}
编辑距离
class Solution {
/**
* 计算将一个字符串转换成另一个字符串所需的最小操作次数。
* 操作包括插入、删除和替换字符。
* @param word1 第一个字符串
* @param word2 第二个字符串
* @return 将word1转换成word2所需的最小操作次数
*/
public int minDistance(String word1, String word2) {
// 获取两个字符串的长度
int len1 = word1.length();
int len2 = word2.length();
// 创建一个二维数组dp，用于存储动态规划的结果
// dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最小操作次数
int dp[][] = new int[len1 + 1][len2 + 1];
// 初始化第一列，表示word1转换为一个空字符串所需的操作次数
// 需要删除word1中的所有字符，因此操作次数等于word1的长度
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
// 初始化第一行，表示一个空字符串转换成word2所需的操作次数
// 需要插入word2中的所有字符，因此操作次数等于word2的长度
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
// 遍历两个字符串的每个字符
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 如果当前字符相同，则不需要额外操作，继承之前的最小操作次数
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 如果当前字符不同，则考虑三种情况：插入、删除和替换
// 取三种操作中的最小值加1（因为至少需要一次操作）
dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1));
}
}
}
// 返回将word1转换成word2所需的最小操作次数
return dp[len1][len2];
}
}回文子串
class Solution {
public int countSubstrings(String s) {
// 获取输入字符串的长度
int len = s.length();
// 将字符串转换为字符数组，便于索引访问
char sCharArr[] = s.toCharArray();
// 创建一个二维布尔数组，用于动态规划存储子问题的解
// dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文
boolean dp[][] = new boolean[len][len];
// 初始化结果变量，用于累计回文子串的数量
int res = 0;
// 从后向前遍历字符串，这样可以确保在处理每个子串时，都考虑了它之前的所有子串
for(int i = len - 1; i >= 0; i--){
// 从当前索引开始，向后遍历字符串，寻找可能的回文子串
for(int j = i; j < len; j++){
// 如果当前字符和比较的字符相同，有两种情况：
// 1. 如果子串长度为1或2，那么它一定是回文
// 2. 如果子串长度大于2，检查去掉首尾字符后，子串是否是回文
if(sCharArr[i] == sCharArr[j]){
if(j - i <= 1){
// 如果子串长度为1或2，直接标记为回文，并增加结果计数
dp[i][j] = true;
res++;
}else if(dp[i + 1][j - 1] == true){
// 如果去掉首尾字符后的子串是回文，那么原子串也是回文
// 增加结果计数，并标记当前子串为回文
res++;
dp[i][j] = true;
}
}
}
}
// 返回计算出的回文子串数量
return res;
}
}最长回文子序列
class Solution {
public int longestPalindromeSubseq(String s) {
// 将字符串转换为字符数组，便于索引访问
char sCharArr[] = s.toCharArray();
// 获取输入字符串的长度
int len = s.length();
// 创建一个二维整数数组，用于动态规划存储子问题的解
// dp[i][j] 表示字符串从索引 i 到 j 的子串的最长回文子序列的长度
int dp[][] = new int[len][len];
// 初始化对角线上的值，单个字符的最长回文子序列长度为1
for(int i = 0 ; i < len; i++){
dp[i][i] = 1;
}
// 从后向前遍历字符串，这样可以确保在处理每个子串时，都考虑了它之前的所有子串
for(int i = len - 1; i >= 0; i--){
// 从当前索引开始，向后遍历字符串，寻找最长回文子序列
for(int j = i + 1 ; j < len; j++){
// 如果当前字符和比较的字符相同，那么最长回文子序列的长度是去掉这两个字符后子串的最长回文子序列长度加2
if(sCharArr[i] == sCharArr[j]){
dp[i][j] = dp[i + 1][j - 1] + 2;
}else{
// 如果当前字符和比较的字符不同，那么最长回文子序列的长度是去掉当前字符或比较字符后子串的最长回文子序列长度的最大值
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
// 返回整个字符串的最长回文子序列的长度
return dp[0][len - 1];
}
}解密数字
class Solution {
// 该方法用于计算给定加密数字ciphertext的解码方式数量
public int crackNumber(int ciphertext) {
// 将整数ciphertext转换为字符串，以便逐位处理
String s = String.valueOf(ciphertext);
// 获取字符串的长度，即数字的位数
int n = s.length();
// 初始化动态规划数组dp，大小为n+1，用于存储到当前位为止的解码方式数量
// dp[i]表示处理到第i位时的解码方式数量
int dp[] = new int[n + 1];
// 初始化基本情况
// dp[0] = 1表示在处理开始前（即处理0位数）有1种方式（空字符串）
dp[0] = 1;
// dp[1] = 1表示处理到第1位时有1种方式（单个字符）
dp[1] = 1;
// 从第2位开始遍历到第n位
for(int i = 2; i <= n; i++){
// dp[i]的初始值是dp[i-1]，即不考虑当前位的情况下的解码方式数量
dp[i] = dp[i - 1];
// 将当前位和前一位组成的两位数转换为整数son
int son = Integer.parseInt(s.substring(i - 2, i));
// 如果son是一个有效的两位数（即在10到25之间）
if(son <= 25 && son >= 10){
// 则将dp[i-2]的值加到dp[i]上，因为这两位可以作为一个整体被解码
dp[i] += dp[i - 2];
}
}
// 返回处理完所有位数后的解码方式数量
return dp[n];
}
}珠宝的最高价值
class Solution {
// 该方法用于计算给定珠宝框架frame的最大价值
public int jewelleryValue(int[][] frame) {
// 获取框架的行数m和列数n
int m = frame.length;
int n = frame[0].length;
// 初始化动态规划数组dp，大小为m×n，用于存储到当前位置为止的最大价值
// dp[i][j]表示处理到第i行第j列时的最大价值
int dp[][] = new int[m][n];
// 遍历框架的每一行
for(int i = 0; i < m; i++){
// 遍历框架的每一列
for(int j = 0 ; j < n ; j++){
// 如果不是第一行，即i > 0
if(i > 0){
// 则dp[i][j]的值至少是dp[i-1][j]的值，即从上面一行移动到当前行
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
}
// 如果不是第一列，即j > 0
if(j > 0){
// 则dp[i][j]的值至少是dp[i][j-1]的值，即从左边一列移动到当前列
dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
}
// 将当前位置的珠宝价值frame[i][j]加到dp[i][j]上
dp[i][j] += frame[i][j];
}
}
// 返回处理完所有行和列后的最大价值，即dp[m-1][n-1]
return dp[m - 1][n - 1];
}
}统计结果概率（难）
第二层循环，是遍历上一次结果每个点的概率，点数加上1后，也就是本次投掷 j + 1点数的概率。不会可以chat一下
class Solution {
public double[] statisticsProbability(int num) {
// 初始化一个长度为6的数组，表示掷一次骰子时每个结果（1到6）的概率都是1/6
double pre[] = {1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};
// 从2次掷骰子开始，一直到num次掷骰子
for(int i = 2; i <= num; i++){
// 计算当前掷骰子次数i时，每种结果的概率数组
// 数组长度为5*i+1，因为掷i次骰子，最大和为5+4+3+...+1=5*i/2，向上取整
double mid[] = new double[5 * i + 1];
// 遍历上一次掷骰子的结果
for(int j = 0 ; j < pre.length; j++){
// 遍历掷骰子的每个面
for(int k = 0; k < 6; k++){
// 更新当前结果的概率，即上一个结果的概率乘以1/6（因为每个面出现的概率都是1/6）
// 并且累加到新的数组mid中对应的位置
mid[j + k] += pre[j] / 6d;
}
}
// 更新pre数组为mid数组，用于下一次迭代
pre = mid;
}
// 返回最终的概率数组
return pre;
}
}破冰游戏
class Solution {
/**
* 游戏冰块破解问题的解决方案。
* 该方法模拟了在游戏过程中冰块被打破的顺序，并返回最后被打破的冰块的位置。
*
* @param num 表示游戏中冰块的总数。
* @param target 表示每次打破冰块时，从当前位置开始计算的目标位置。
* @return 返回最后被打破的冰块的位置。
*/
public int iceBreakingGame(int num, int target) {
// 初始化位置变量pos为0，表示从第一个冰块开始。
int pos = 0;
// 从第二个冰块开始遍历，因为第一个冰块默认是起始位置。
for(int i = 2; i <= num; i++){
// 计算下一个被打破的冰块的位置。
// 这里使用(pos + target) % i来模拟循环，因为冰块是环形排列的。
// 例如，如果pos是3，target是2，num是5，那么下一个位置是(3+2)%5=0。
pos = (pos + target) % i;
}
// 返回最后被打破的冰块的位置。
return pos;
}
}原文地址：https://blog.csdn.net/2302_80490510/article/details/144049475
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！