Leetcode+Java+动态规划VIII

YSRM

402人浏览 · 2025-09-24 17:13:37

YSRM · 2025-09-24 17:13:37 发布

714.买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 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
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
提示：

1 <= prices.length <= 5 * 104

1 <= prices[i] < 5 * 104

0 <= fee < 5 * 104

原理

定义状态：

使用二维数组 dp[i][j]，表示第 i 天处于状态 j 的最大利润：

j = 0：持有股票。

j = 1：不持有股票。

目标是 dp[n-1][1]，因为最后一天不持有股票（卖出或不交易）产生最大利润。

初始化：

第0天：

dp[0][0] = -prices[0]：持有股票（买入）。

dp[0][1] = 0：不持有股票（未交易）。

状态转移：

对于每一天 i（从1到 n-1）：

持有股票（dp[i][0]）：

继续持有：dp[i-1][0]。

前一天不持有，当天买入：dp[i-1][1] - prices[i]。

取最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])。

不持有股票（dp[i][1]）：

继续不持有：dp[i-1][1]。

前一天持有，当天卖出（扣除手续费）：dp[i-1][0] + prices[i] - fee。

取最大值：dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)。

手续费在卖出时扣除，确保每笔交易（买入-卖出）只支付一次费用。

优化可能性：

状态只依赖前一天，可用两个变量（hold 和 notHold）代替 dp 数组，优化空间到 O(1)。

当前代码使用二维数组，逻辑更直观。

时间复杂度：

遍历天数：O(n)，n 为 prices.length。

每次更新两个状态：O(1)。

总时间复杂度：O(n)。

空间复杂度：

使用二维数组 dp[n][2]：O(n)。

代码

import java.util.*;

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // 特殊情况：如果只有一天，无法交易，返回0
        if (prices.length == 1) return 0;
        
        // 创建二维dp数组，dp[i][0]表示第i天持有股票的最大利润，dp[i][1]表示不持有股票的最大利润
        int[][] dp = new int[prices.length][2];
        
        // 初始化第0天状态
        dp[0][0] = -prices[0]; // 持有股票（买入）
        dp[0][1] = 0;         // 不持有股票（未交易）
        
        // 遍历从第1天到最后一天
        for (int i = 1; i < prices.length; i++) {
            // 持有股票的最大利润：
            // 1. 前一天已持有：dp[i-1][0]
            // 2. 前一天不持有，当天买入：dp[i-1][1] - prices[i]
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            
            // 不持有股票的最大利润：
            // 1. 前一天不持有：dp[i-1][1]
            // 2. 前一天持有，当天卖出（扣除手续费）：dp[i-1][0] + prices[i] - fee
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        
        // 返回最后一天不持有股票的最大利润
        return dp[prices.length - 1][1];
    }
}

300.最长递增子序列

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

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

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

1 <= nums.length <= 2500

-104 <= nums[i] <= 104

原理

定义状态：

使用数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。

目标是找到 dp[i] 中的最大值，表示整个数组的最长递增子序列长度。

初始化：

dp[0] = 1，因为以第一个元素结尾的子序列长度至少为1（仅包含自身）。

如果数组长度为1，直接返回1。

初始化全局最大长度 max = 1。

状态转移：

对于每个元素 nums[i]（i 从1到 n-1）：

初始化 dp[i] = 1（最短为自身）。

检查所有之前的元素 nums[j]（j 从0到 i-1）：

如果 nums[i] > nums[j]，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后。

更新 dp[i] = max(dp[i], dp[j] + 1)，表示在 dp[j] 基础上加1。

更新全局最大长度 max = max(max, dp[i])。

这样，dp[i] 记录了以 nums[i] 结尾的最长递增子序列长度。

时间复杂度：

外层循环：O(n)，n 为数组长度。

内层循环：O(i)，最坏为 O(n)。

总时间复杂度：O(n^2)。

空间复杂度：

使用 dp 数组：O(n)。

优化可能性：

可用二分查找优化到 O(n log n)，通过维护一个数组记录当前长度下最小的尾元素，但当前代码使用朴素动态规划。

代码

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 特殊情况：如果数组长度为1，返回1
        if (nums.length == 1) return 1;
        
        // 初始化最大递增子序列长度为1
        int max = 1;
        
        // 创建dp数组，dp[i]表示以nums[i]结尾的最长递增子序列长度
        int[] dp = new int[nums.length];
        
        // 初始化：以第0个元素结尾的子序列长度为1
        dp[0] = 1;
        
        // 遍历数组，从第1个元素开始
        for (int i = 1; i < nums.length; i++) {
            // 初始化以nums[i]结尾的子序列长度为1（仅包含自身）
            dp[i] = 1;
            
            // 检查所有之前的元素j（0到i-1）
            for (int j = 0; j < i; j++) {
                // 如果nums[i] > nums[j]，可以在dp[j]的基础上加1
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            // 更新全局最大长度
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        
        // 返回最长递增子序列的长度
        return max;
    }
}

674.最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
提示：

1 <= nums.length <= 104

-109 <= nums[i] <= 109

原理

import java.util.*;

class Solution {
public int findLengthOfLCIS(int[] nums) {
// 特殊情况：如果数组长度为1，返回1
if (nums.length == 1) return 1;

// 初始化最大连续递增子序列长度为1
int max = 1;

// 创建dp数组，dp[i]表示以nums[i]结尾的最长连续递增子序列长度
int[] dp = new int[nums.length];

// 初始化：以第0个元素结尾的子序列长度为1
dp[0] = 1;

// 遍历数组，从第1个元素开始
for (int i = 1; i < nums.length; i++) {
// 如果当前元素大于前一个元素，子序列可延续
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
// 否则，当前元素开始一个新的子序列，长度为1
dp[i] = 1;
}

// 更新全局最大长度
if (max < dp[i]) {
max = dp[i];
}
}

// 返回最长连续递增子序列的长度
return max;
}
}

代码

import java.util.*;

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // 特殊情况：如果数组长度为1，返回1
        if (nums.length == 1) return 1;
        
        // 初始化最大连续递增子序列长度为1
        int max = 1;
        
        // 创建dp数组，dp[i]表示以nums[i]结尾的最长连续递增子序列长度
        int[] dp = new int[nums.length];
        
        // 初始化：以第0个元素结尾的子序列长度为1
        dp[0] = 1;
        
        // 遍历数组，从第1个元素开始
        for (int i = 1; i < nums.length; i++) {
            // 如果当前元素大于前一个元素，子序列可延续
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                // 否则，当前元素开始一个新的子序列，长度为1
                dp[i] = 1;
            }
            
            // 更新全局最大长度
            if (max < dp[i]) {
                max = dp[i];
            }
        }
        
        // 返回最长连续递增子序列的长度
        return max;
    }
}

718.最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
提示：

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 100

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度。

目标是找到 dp[i][j] 中的最大值，表示最长公共子数组的长度。

初始化：

dp 数组初始化为0（默认值）。

使用 dp[i][j] 对应 nums1[i-1] 和 nums2[j-1]，因此数组大小为 (nums1.length + 1) x (nums2.length + 1)，边界（i=0 或 j=0）表示空数组，长度为0。

状态转移：

遍历 nums1 和 nums2 的所有位置（i 从1到 nums1.length，j 从1到 nums2.length）：

如果 nums1[i-1] == nums2[j-1]，说明当前元素相同，可以在以 nums1[i-2] 和 nums2[j-2] 结尾的公共子数组后加1：

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

如果不相等，公共子数组断开，dp[i][j] = 0（默认值，无需显式设置）。

在每次更新 dp[i][j] 时，更新全局最大长度 result = max(result, dp[i][j])。

时间复杂度：

双重循环：O(m * n)，其中 m = nums1.length，n = nums2.length。

每次操作（比较、加法）：O(1)。

总时间复杂度：O(m * n)。

空间复杂度：

使用二维数组 dp[m+1][n+1]：O(m * n)。

优化：可用滚动数组（一维数组）或滑动窗口方法，空间可降到 O(min(m, n))。

代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // 初始化最长公共子数组长度
        int result = 0;
        
        // 创建dp数组，dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的公共子数组长度
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        
        // 遍历nums1和nums2的所有位置
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                // 如果当前元素相等，公共子数组长度为前一个位置的长度+1
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 更新全局最大长度
                    result = Math.max(result, dp[i][j]);
                }
                // 如果不相等，dp[i][j]保持0（无需显式设置，因为数组默认0）
            }
        }
        
        // 返回最长公共子数组长度
        return result;
    }
}

1143.最长公共子序列

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

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

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

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

示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
提示：

1 <= text1.length, text2.length <= 1000

text1 和 text2 仅由小写英文字符组成。

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示 text1[0:i]（前 i+1 个字符）和 text2[0:j]（前 j+1 个字符）的最长公共子序列长度。

目标是 dp[len1-1][len2-1]，表示整个字符串的最长公共子序列长度。

初始化：

dp[0][0]：如果首字符相同（text1[0] == text2[0]），则 dp[0][0] = 1；否则为0。

第一列（dp[i][0]）：text1[0:i] 与 text2[0] 的公共子序列：

如果 text1[i] == text2[0]，dp[i][0] = 1。

否则，继承上一行：dp[i][0] = dp[i-1][0]。

第一行（dp[0][j]）：text1[0] 与 text2[0:j] 的公共子序列：

如果 text2[j] == text1[0]，dp[0][j] = 1。

否则，继承前一列：dp[0][j] = dp[0][j-1]。

状态转移：

对于每个位置 (i, j)（i 从1到 len1-1，j 从1到 len2-1）：

如果 text1[i] == text2[j]，当前字符可加入公共子序列：

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

如果不相等，取不包含当前字符的最大值：

dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

这样，dp[i][j] 记录了以 text1[0:i] 和 text2[0:j] 结尾的最长公共子序列长度。

时间复杂度：

双重循环：O(len1 * len2)，其中 len1 = text1.length，len2 = text2.length。

每次操作（比较、加法）：O(1)。

总时间复杂度：O(len1 * len2)。

空间复杂度：

使用二维数组 dp[len1][len2]：O(len1 * len2)。

优化：可用滚动数组，空间可降到 O(min(len1, len2))。

代码

import java.util.*;

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 获取两个字符串的长度
        int len1 = text1.length(), len2 = text2.length();
        
        // 创建dp数组，dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度
        int[][] dp = new int[len1][len2];
        
        // 初始化第一格：如果首字符相同，dp[0][0]=1，否则为0
        if (text1.charAt(0) == text2.charAt(0)) {
            dp[0][0] = 1;
        }
        
        // 初始化第一列：text1[0:i]与text2[0]的最长公共子序列
        for (int i = 1; i < len1; i++) {
            if (text1.charAt(i) == text2.charAt(0)) {
                dp[i][0] = 1; // 找到公共字符，长度为1
            } else {
                dp[i][0] = dp[i - 1][0]; // 继承上一行的值
            }
        }
        
        // 初始化第一行：text1[0]与text2[0:j]的最长公共子序列
        for (int j = 1; j < len2; j++) {
            if (text2.charAt(j) == text1.charAt(0)) {
                dp[0][j] = 1; // 找到公共字符，长度为1
            } else {
                dp[0][j] = dp[0][j - 1]; // 继承前一列的值
            }
        }
        
        // 填充dp数组
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                // 如果当前字符相同，公共子序列长度为前一状态加1
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 否则，取不包含当前字符的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 返回text1和text2的最长公共子序列长度
        return dp[len1 - 1][len2 - 1];
    }
}

1035.不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

nums1[i] == nums2[j]

且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3
示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2
提示：

1 <= nums1.length, nums2.length <= 500

1 <= nums1[i], nums2[j] <= 2000

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示 nums1[0:i]（前 i+1 个元素）和 nums2[0:j]（前 j+1 个元素）能绘制的最大不相交连线数。

目标是 dp[len1-1][len2-1]，表示整个数组的最大连线数。

初始化：

dp[0][0]：如果 nums1[0] == nums2[0]，则 dp[0][0] = 1；否则为0。

第一列（dp[i][0]）：nums1[0:i] 与 nums2[0] 的连线数：

如果 nums1[i] == nums2[0]，dp[i][0] = 1。

否则，继承上一行：dp[i][0] = dp[i-1][0]。

第一行（dp[0][j]）：nums1[0] 与 nums2[0:j] 的连线数：

如果 nums2[j] == nums1[0]，dp[0][j] = 1。

否则，继承前一列：dp[0][j] = dp[0][j-1]。

状态转移：

对于每个位置 (i, j)（i 从1到 len1-1，j 从1到 len2-1）：

如果 nums1[i] == nums2[j]，可以绘制一条连线：

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

如果不相等，取不包含当前元素的最大连线数：

dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

这样，dp[i][j] 记录了以 nums1[0:i] 和 nums2[0:j] 结尾的最大连线数。

等价于LCS：

问题等价于求 nums1 和 nums2 的最长公共子序列长度，因为连线必须保持相对顺序（子序列），且不能交叉（保证子序列的顺序一致性）。

时间复杂度：

双重循环：O(len1 * len2)，其中 len1 = nums1.length，len2 = nums2.length。

每次操作（比较、加法）：O(1)。

总时间复杂度：O(len1 * len2)。

空间复杂度：

使用二维数组 dp[len1][len2]：O(len1 * len2)。

优化：可用滚动数组，空间可降到 O(min(len1, len2))。

代码

import java.util.*;

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 获取两个数组的长度
        int len1 = nums1.length, len2 = nums2.length;
        
        // 创建dp数组，dp[i][j]表示nums1[0:i]和nums2[0:j]的最大不相交连线数
        int[][] dp = new int[len1][len2];
        
        // 初始化第一格：如果首元素相同，可绘制1条连线
        if (nums1[0] == nums2[0]) {
            dp[0][0] = 1;
        }
        
        // 初始化第一列：nums1[0:i]与nums2[0]的最大连线数
        for (int i = 1; i < len1; i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1; // 找到相同元素，连线数为1
            } else {
                dp[i][0] = dp[i - 1][0]; // 继承上一行的值
            }
        }
        
        // 初始化第一行：nums1[0]与nums2[0:j]的最大连线数
        for (int j = 1; j < len2; j++) {
            if (nums2[j] == nums1[0]) {
                dp[0][j] = 1; // 找到相同元素，连线数为1
            } else {
                dp[0][j] = dp[0][j - 1]; // 继承前一列的值
            }
        }
        
        // 填充dp数组
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                // 如果当前元素相同，可以绘制一条连线
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 否则，取不包含当前元素的最大连线数
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 返回nums1和nums2的最大不相交连线数
        return dp[len1 - 1][len2 - 1];
    }
}

53.最大子数组合

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：

1 <= nums.length <= 105

-104 <= nums[i] <= 104

原理

定义状态：

使用数组 dp，其中 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。

目标是找到 dp[i] 中的最大值，表示整个数组的最大子数组和。

初始化：

dp[0] = nums[0]，以第一个元素结尾的子数组和就是 nums[0]。

如果数组长度为1，直接返回 nums[0]。

初始化全局最大和 max = dp[0]。

状态转移：

对于每个元素 nums[i]（i 从1到 len-1）：

以 nums[i] 结尾的最大子数组和有两种选择：

单独使用 nums[i]（丢弃前面的子数组）。

在以 nums[i-1] 结尾的最大子数组和 dp[i-1] 后加上 nums[i]。

状态转移公式：dp[i] = max(nums[i], dp[i-1] + nums[i])。

更新全局最大和：max = max(max, dp[i])。

Kadane 算法：

上述动态规划实际上是 Kadane 算法的实现，核心思想是维护一个当前子数组和（dp[i]），如果前面的和为负数（dp[i-1] < 0），则重新开始以当前元素为起点。

全局最大和 max 记录遍历过程中遇到的最大子数组和。

时间复杂度：

遍历数组一次：O(n)，n 为数组长度。

每次操作（比较、加法）：O(1)。

总时间复杂度：O(n)。

空间复杂度：

使用 dp 数组：O(n)。

优化：由于状态只依赖前一个元素，可用单个变量代替 dp 数组，空间可降到 O(1)。

代码

import java.util.*;

class Solution {
    public int maxSubArray(int[] nums) {
        // 获取数组长度
        int len = nums.length;
        
        // 特殊情况：如果数组长度为1，直接返回唯一元素
        if (len == 1) return nums[0];
        
        // 创建dp数组，dp[i]表示以nums[i]结尾的连续子数组的最大和
        int[] dp = new int[len];
        
        // 初始化：以第0个元素结尾的子数组和为nums[0]
        dp[0] = nums[0];
        
        // 初始化最大和为dp[0]
        int max = dp[0];
        
        // 遍历数组，从第1个元素开始
        for (int i = 1; i < len; i++) {
            // 以nums[i]结尾的最大子数组和：
            // 1. 单独使用nums[i]
            // 2. 在前一天的最大子数组和dp[i-1]后加上nums[i]
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            
            // 更新全局最大和
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        
        // 返回最大子数组和
        return max;
    }
}

392.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：

0 <= s.length <= 100

0 <= t.length <= 10^4

两个字符串都只由小写字符组成。

原理

定义状态：

dp[i][j] 表示 s[0:i] 和 t[0:j] 的最长公共子序列长度。

如果 dp[len1-1][len2-1] == len1，说明 s 是 t 的子序列。

初始化：

dp[0][0]：如果 s[0] == t[0]，dp[0][0] = 1。

第一列（dp[i][0]）：s[0:i] 与 t[0] 的公共子序列长度。

第一行（dp[0][j]）：s[0] 与 t[0:j] 的公共子序列长度。

状态转移：

如果 s[i] == t[j]，dp[i][j] = dp[i-1][j-1] + 1。

如果不相等，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

提前检查：如果 dp[i][j] == len1，可提前返回 true。

时间复杂度：

双重循环：O(len1 * len2)，其中 len1 = s.length()，len2 = t.length()。

每次操作：O(1)。

总时间复杂度：O(len1 * len2)。

空间复杂度：

使用 dp[len1][len2] 数组：O(len1 * len2)。

代码

import java.util.*;

class Solution {
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        // 如果s的长度大于t，s不可能是t的子序列
        if (len1 > len2) return false;
        // 如果s为空字符串，它是任何字符串的子序列
        if (len1 == 0) return true;
        
        // 创建dp数组，dp[i][j]表示s[0:i]和t[0:j]的最长公共子序列长度
        int[][] dp = new int[len1][len2];
        
        // 初始化第一格
        if (s.charAt(0) == t.charAt(0)) dp[0][0] = 1;
        
        // 初始化第一列：s[0:i]与t[0]的最长公共子序列
        for (int i = 1; i < len1; i++) {
            if (s.charAt(i) == t.charAt(0)) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
            // 提前检查是否已找到s的长度
            if (dp[i][0] == len1) return true;
        }
        
        // 初始化第一行：s[0]与t[0:j]的最长公共子序列
        for (int j = 1; j < len2; j++) {
            if (t.charAt(j) == s.charAt(0)) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = dp[0][j - 1];
            }
            if (dp[0][j] == len1) return true;
        }
        
        // 填充dp数组
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                // 提前检查是否已找到s的长度
                if (dp[i][j] == len1) return true;
            }
        }
        
        // 如果dp[len1-1][len2-1]等于s的长度，说明s是t的子序列
        return dp[len1 - 1][len2 - 1] == len1;
    }
}

115.不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag
提示：

1 <= s.length, t.length <= 1000

s 和 t 由英文字母组成

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示 t[0:i]（t 的前 i+1 个字符）在 s[0:j]（s 的前 j+1 个字符）中作为子序列的个数。

目标是 dp[len2-1][len1-1]，表示整个 t 在整个 s 中的子序列个数。

初始化：

如果 len1 < len2，t 不可能是 s 的子序列，返回0。

第一行（dp[0][j]）：t 的第一个字符在 s[0:j] 中的匹配次数：

dp[0][0] = 1 如果 s[0] == t[0]，否则为0。

对于 j > 0，dp[0][j] = dp[0][j-1] + (s[j] == t[0] ? 1 : 0)，累加匹配次数。

状态转移：

对于 i 从1到 len2-1，j 从 i 到 len1-1（因为子序列长度至少为 i+1，需 j >= i）：

如果 s[j] == t[i]，可以选择使用或不使用 s[j]：

使用 s[j]：dp[i-1][j-1]（匹配 t[0:i-1] 和 s[0:j-1]，加上当前匹配）。

不使用 s[j]：dp[i][j-1]（匹配 t[0:i] 和 s[0:j-1]）。

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

如果不相等，只能不使用 s[j]：

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

注意：j 从 i 开始优化了循环，因为 t[0:i] 的长度为 i+1，需要 s 至少有 i+1 个字符。

时间复杂度：

双重循环：O(len2 * len1)，但内层循环从 j=i 开始，实际复杂度接近 O(len1 * len2)。

每次操作：O(1)。

总时间复杂度：O(len1 * len2)。

空间复杂度：

使用 dp[len2][len1] 数组：O(len1 * len2)。

优化：可用滚动数组，空间可降到 O(len1)。

代码

import java.util.*;

class Solution {
    public int numDistinct(String s, String t) {
        // 获取字符串长度
        int len1 = s.length(), len2 = t.length();
        
        // 如果s的长度小于t，t不可能是s的子序列，返回0
        if (len1 < len2) return 0;
        
        // 创建dp数组，dp[i][j]表示t[0:i]在s[0:j]中的子序列个数
        int[][] dp = new int[len2][len1];
        
        // 初始化第一行：t的第一个字符在s[0:j]中的匹配次数
        if (s.charAt(0) == t.charAt(0)) dp[0][0] = 1;
        for (int i = 1; i < len1; i++) {
            dp[0][i] = dp[0][i - 1]; // 继承前一列的结果
            if (t.charAt(0) == s.charAt(i)) {
                dp[0][i] += 1; // 如果匹配，增加1
            }
        }
        
        // 填充dp数组
        for (int i = 1; i < len2; i++) {
            for (int j = i; j < len1; j++) {
                // 如果当前字符匹配
                if (s.charAt(j) == t.charAt(i)) {
                    // 使用s[j]：t[0:i-1]在s[0:j-1]的子序列数
                    // 不使用s[j]：t[0:i]在s[0:j-1]的子序列数
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                } else {
                    // 不使用s[j]：继承前一列的结果
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        
        // 返回t在s中的子序列个数
        return dp[len2 - 1][len1 - 1];
    }
}

583.两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
提示：

1 <= word1.length, word2.length <= 500

word1 和 word2 只包含小写英文字母

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示 word1[0:i]（前 i+1 个字符）和 word2[0:j]（前 j+1 个字符）的最长公共子序列长度。

目标是 dp[len1-1][len2-1]，表示整个字符串的LCS长度。

最小步数 = len1 + len2 - 2 * LCS，因为LCS部分的字符保留，其余字符需删除。

初始化：

dp[0][0]：如果 word1[0] == word2[0]，则 dp[0][0] = 1；否则为0。

第一列（dp[i][0]）：word1[0:i] 与 word2[0] 的LCS长度。

第一行（dp[0][j]）：word1[0] 与 word2[0:j] 的LCS长度。

状态转移：

对于每个位置 (i, j)（i 从1到 len1-1，j 从1到 len2-1）：

如果 word1[i] == word2[j]，当前字符可加入LCS：

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

如果不相等，取不包含当前字符的最大值：

dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终，dp[len1-1][len2-1] 为LCS长度。

计算结果：

最小步数 = len1 + len2 - 2 * dp[len1-1][len2-1]，因为LCS部分的字符保留，其余字符需从 word1 和 word2 中删除。

时间复杂度：

双重循环：O(len1 * len2)。

每次操作：O(1)。

总时间复杂度：O(len1 * len2)。

空间复杂度：

使用 dp[len1][len2] 数组：O(len1 * len2)。

优化：可用滚动数组，空间可降到 O(min(len1, len2))。

代码

import java.util.*;

class Solution {
    public int minDistance(String word1, String word2) {
        // 获取两个字符串的长度
        int len1 = word1.length(), len2 = word2.length();
        
        // 创建dp数组，dp[i][j]表示word1[0:i]和word2[0:j]的最长公共子序列长度
        int[][] dp = new int[len1][len2];
        
        // 初始化第一格：如果首字符相同，dp[0][0]=1
        if (word1.charAt(0) == word2.charAt(0)) dp[0][0] = 1;
        
        // 初始化第一列：word1[0:i]与word2[0]的最长公共子序列
        for (int i = 1; i < len1; i++) {
            if (word1.charAt(i) == word2.charAt(0)) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        
        // 初始化第一行：word1[0]与word2[0:j]的最长公共子序列
        for (int j = 1; j < len2; j++) {
            if (word2.charAt(j) == word1.charAt(0)) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = dp[0][j - 1];
            }
        }
        
        // 填充dp数组
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果字符不同，取上或左的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 计算最小步数：总长度减去两倍的最长公共子序列长度
        int ans = len1 + len2 - 2 * dp[len1 - 1][len2 - 1];
        return ans;
    }
}

72.编辑距离

给你两个单词 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')
提示：

0 <= word1.length, word2.length <= 500

word1 和 word2 由小写英文字母组成

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示将 word1[0:i]（前 i+1 个字符）转换为 word2[0:j]（前 j+1 个字符）的最小操作数。

目标是 dp[len1-1][len2-1]，表示整个字符串的编辑距离。

初始化：

如果任一字符串为空，操作数为另一字符串的长度：max(len1, len2)。

dp[0][0]：如果 word1[0] != word2[0]，需要1次替换；否则为0。

第一列（dp[i][0]）：将 word1[0:i] 转换为 word2[0]：

如果 word1[i] == word2[0]，需要删除前 i 个字符：dp[i][0] = i。

否则，继承上一状态并删除 word1[i]：dp[i][0] = dp[i-1][0] + 1。

第一行（dp[0][j]）：将 word1[0] 转换为 word2[0:j]：

如果 word2[j] == word1[0]，需要删除 word2 的前 j 个字符：dp[0][j] = j。

否则，继承前一状态并插入 word2[j]：dp[0][j] = dp[0][j-1] + 1.

状态转移：

对于每个位置 (i, j)（i 从1到 len1-1，j 从1到 len2-1）：

如果 word1[i] == word2[j]，无需操作：dp[i][j] = dp[i-1][j-1]。

如果不相等，考虑三种操作：

替换：dp[i-1][j-1] + 1（将 word1[i] 替换为 word2[j]）。

删除：dp[i-1][j] + 1（删除 word1[i]）。

插入：dp[i][j-1] + 1（插入 word2[j]）。

取最小值：dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)。

时间复杂度：

双重循环：O(len1 * len2)。

每次操作：O(1)。

总时间复杂度：O(len1 * len2)。

空间复杂度：

使用 dp[len1][len2] 数组：O(len1 * len2)。

优化：可用滚动数组，空间可降到 O(min(len1, len2))。

代码

import java.util.*;

class Solution {
    public int minDistance(String word1, String word2) {
        // 获取两个字符串的长度
        int len1 = word1.length(), len2 = word2.length();
        
        // 边界情况：如果任一字符串为空，操作数为另一字符串的长度
        if (len1 == 0 || len2 == 0) {
            return Math.max(len1, len2);
        }
        
        // 创建dp数组，dp[i][j]表示将word1[0:i]转换为word2[0:j]的最小操作数
        int[][] dp = new int[len1][len2];
        
        // 初始化第一格：如果首字符不同，需要1次替换
        if (word1.charAt(0) != word2.charAt(0)) dp[0][0] = 1;
        
        // 初始化第一列：将word1[0:i]转换为word2[0]
        for (int i = 1; i < len1; i++) {
            if (word1.charAt(i) == word2.charAt(0)) {
                dp[i][0] = i; // 删除word1的前i个字符
            } else {
                dp[i][0] = dp[i - 1][0] + 1; // 删除word1[i]，继承上一状态
            }
        }
        
        // 初始化第一行：将word1[0]转换为word2[0:j]
        for (int j = 1; j < len2; j++) {
            if (word2.charAt(j) == word1.charAt(0)) {
                dp[0][j] = j; // 删除word2的前j个字符
            } else {
                dp[0][j] = dp[0][j - 1] + 1; // 插入word2[j]，继承前一状态
            }
        }
        
        // 填充dp数组
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 字符相同，无需操作
                } else {
                    // 字符不同，取以下三种操作的最小值：
                    // 1. 替换：dp[i-1][j-1] + 1
                    // 2. 删除word1[i]：dp[i-1][j] + 1
                    // 3. 插入word2[j]：dp[i][j-1] + 1
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, 
                                       Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        
        // 返回将word1转换为word2的最小操作数
        return dp[len1 - 1][len2 - 1];
    }
}

647.回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：

1 <= s.length <= 1000

s 由小写英文字母组成

原理

定义状态：

使用二维布尔数组 dp，其中 dp[i][j] 表示子串 s[j:i]（从索引 j 到 i）是否为回文。

目标是统计所有 dp[i][j] == true 的子串数量。

初始化：

初始时，dp 数组全为 false。

使用变量 result 记录回文子串的总数。

状态转移：

遍历所有可能的子串（i 从0到 len-1，j 从0到 i）：

如果 s[i] == s[j]（首尾字符相同）：

如果子串长度为1（i == j）或2（i - j == 1），直接是回文：

dp[i][j] = true，result++。

如果长度大于2，检查内部子串 s[j+1:i-1] 是否为回文（dp[i-1][j+1]）：

如果 dp[i-1][j+1] == true，则 dp[i][j] = true，result++。

如果 s[i] != s[j]，子串 s[j:i] 不是回文，dp[i][j] = false（默认）。

时间复杂度：

双重循环：O(len^2)，其中 len 是字符串长度。

每次操作（比较、赋值）：O(1)。

总时间复杂度：O(len^2)。

空间复杂度：

使用 dp[len][len] 数组：O(len^2)。

优化：可用其他方法（如中心扩展法）将空间降到 O(1)。

代码

import java.util.*;

class Solution {
    public int countSubstrings(String s) {
        // 获取字符串长度
        int len = s.length();
        // 初始化回文子串计数
        int result = 0;
        
        // 创建dp数组，dp[i][j]表示s[j:i]是否为回文子串
        boolean[][] dp = new boolean[len][len];
        
        // 遍历所有可能的子串（从右到左，i >= j）
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                // 如果首尾字符相同
                if (s.charAt(i) == s.charAt(j)) {
                    // 长度为1或2的子串（i-j <= 1），直接是回文
                    if (i - j <= 1) {
                        result++;
                        dp[i][j] = true;
                    }
                    // 长度大于2，检查内部子串是否为回文
                    else if (dp[i - 1][j + 1]) {
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        
        // 返回回文子串总数
        return result;
    }
}

516.最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：

1 <= s.length <= 1000

s 仅由小写英文字母组成

原理

定义状态：

使用二维数组 dp，其中 dp[i][j] 表示子串 s[i:j]（从索引 i 到 j）的最长回文子序列长度。

目标是 dp[0][len-1]，表示整个字符串的最长回文子序列长度。

初始化：

对于单个字符（i == j），dp[i][i] = 1，因为单个字符是长度为1的回文。

dp 数组其他部分默认初始化为0。

状态转移：

从后往前遍历 i（从 len-1 到0），j 从 i+1 到 len-1：

如果 s[i] == s[j]，首尾字符可同时加入回文子序列：

dp[i][j] = dp[i+1][j-1] + 2（内部子序列长度加2）。

如果 s[i] != s[j]，取不包含首或尾字符的最大值：

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

遍历顺序确保依赖的子问题（dp[i+1][j-1], dp[i+1][j], dp[i][j-1]）已计算。

时间复杂度：

双重循环：O(len^2)，其中 len 是字符串长度。

每次操作：O(1)。

总时间复杂度：O(len^2)。

空间复杂度：

使用 dp[len][len] 数组：O(len^2)。

优化：可用滚动数组或一维数组，空间可降到 O(len)。

代码

import java.util.*;

public class Solution {
    public int longestPalindromeSubseq(String s) {
        // 获取字符串长度
        int len = s.length();
        
        // 创建dp数组，dp[i][j]表示s[i:j]的最长回文子序列长度
        int[][] dp = new int[len][len];
        
        // 从后往前遍历，确保依赖的子问题已计算
        for (int i = len - 1; i >= 0; i--) {
            // 单个字符是回文，长度为1
            dp[i][i] = 1;
            // 遍历j从i+1到len-1，检查子串s[i:j]
            for (int j = i + 1; j < len; j++) {
                // 如果首尾字符相同
                if (s.charAt(i) == s.charAt(j)) {
                    // 回文长度为内部子序列长度加2
                    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];
    }
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError