企业官网建设流程全解析

1. 动态规划实战：背包问题的三种经典变体

动态规划是算法学习中的核心内容，而背包问题又是动态规划中最具代表性的题型。今天我将分享三种背包问题的变体解法，这些题目都来自力扣中等难度题库，但实际考察频率很高。我会从问题分析、状态转移推导到代码实现，带你完整走一遍解题思路。

2. 最后一块石头的重量 II

2.1 问题重述与转化

题目描述：有一堆石头，用整数数组 stones 表示，其中 stones[i] 表示第 i 块石头的重量。每次可以任意选两块石头进行粉碎，假设石头重量分别为 x 和 y，粉碎后可能得到三种结果：

1. x == y：两块石头完全粉碎
2. x > y：剩下重量为 x - y 的石头
3. x < y：剩下重量为 y - x 的石头

最终最多只会剩下一块石头，返回此石头最小的可能重量。

这道题看似是模拟题，实际上可以转化为经典的背包问题。关键在于理解题目本质：我们需要将石头分成两堆，使两堆的重量差最小。这就是典型的"分割等和子集"问题的变种。

2.2 动态规划解法详解

2.2.1 状态定义

定义 dp[i] 表示背包容量为 i 时能装下的最大石头重量。我们的目标是找到一个容量为 sum/2 的背包能装下的最大重量，其中 sum 是所有石头的总重量。

2.2.2 状态转移方程

对于每块石头，我们有两种选择：

1. 不放入背包：dp[j] 保持不变
2. 放入背包：dp[j] = max(dp[j], stones[i] + dp[j - stones[i]])

注意这里需要从后向前遍历，避免重复计算（这是01背包问题的经典处理方式）。

2.2.3 完整代码实现

public int lastStoneWeightII(int[] stones) { int sum = IntStream.of(stones).sum(); int target = sum / 2; int[] dp = new int[target + 1]; for (int stone : stones) { for (int j = target; j >= stone; j--) { dp[j] = Math.max(dp[j], stone + dp[j - stone]); } } return sum - 2 * dp[target]; }

2.3 复杂度分析与优化

时间复杂度：O(n * target)，其中 n 是石头数量，target 是 sum/2 空间复杂度：O(target)

注意：在实际面试中，可以提到如果 sum 很大时，可以考虑使用位运算优化或者剪枝策略。

3. 目标和问题

3.1 问题描述与数学转化

给定一个非负整数数组 nums 和一个整数 target，向数组中的每个整数前添加 '+' 或 '-'，然后串联起来构成一个表达式，返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

这道题的关键在于数学转化：

1. 设正数和为 left，负数和绝对值为 right
2. 有 left - right = target
3. 又因为 left + right = sum（数组总和）
4. 联立可得 left = (sum + target) / 2

这样问题就转化为：在数组中找出若干数，使其和为 (sum + target)/2 的组合数。

3.2 动态规划解法

3.2.1 状态定义

定义 dp[i][j] 表示使用前 i 个物品装满容量为 j 的背包的方法数。

3.2.2 状态转移方程

对于每个数字 nums[i]，我们有两种选择：

1. 不选：dp[i][j] = dp[i-1][j]
2. 选：dp[i][j] += dp[i-1][j - nums[i]]

初始化时需要注意：

• dp[0][0] = 1（空集也是一种方案）
• 处理 nums[i] = 0 的特殊情况

3.2.3 完整代码实现

public int findTargetSumWays(int[] nums, int target) { int sum = IntStream.of(nums).sum(); if ((sum + target) % 2 != 0 || sum < Math.abs(target)) { return 0; } int bag = (target + sum) / 2; int[] dp = new int[bag + 1]; dp[0] = 1; for (int num : nums) { for (int j = bag; j >= num; j--) { dp[j] += dp[j - num]; } } return dp[bag]; }

3.3 注意事项

1. 边界条件检查：(sum + target) 必须是偶数且 sum ≥ |target|
2. 空间优化：使用一维数组代替二维数组
3. 处理0的特殊情况：0可以选或不选，不影响和

4. 一和零问题

4.1 问题描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n，请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1。

这是典型的多维背包问题，每个字符串都有两个维度的"重量"（0的个数和1的个数），我们需要在不超过容量限制的情况下，选择最多的物品。

4.2 动态规划解法

4.2.1 状态定义

定义 dp[i][j] 表示使用 i 个 0 和 j 个 1 能组成的最大子集大小。

4.2.2 状态转移方程

对于每个字符串，统计其0的个数 zeros 和1的个数 ones： dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)

同样需要从后向前遍历，避免重复计算。

4.2.3 完整代码实现

public int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; for (String str : strs) { int zeros = 0, ones = 0; for (char c : str.toCharArray()) { if (c == '0') zeros++; else ones++; } for (int i = m; i >= zeros; i--) { for (int j = n; j >= ones; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1); } } } return dp[m][n]; }

4.3 优化与扩展

1. 预处理：可以预先计算每个字符串的0和1的个数，避免重复计算
2. 空间优化：虽然已经是二维，但可以进一步考虑滚动数组
3. 扩展：类似思路可以解决更多维度的背包问题

5. 动态规划解题心得

在实际解决动态规划问题时，我总结了以下几个关键步骤：

1. 问题转化：很多看似不是背包问题的问题，经过适当转化后可以套用背包模型。比如"最后一块石头"转化为分割子集问题。

2. 状态定义：明确 dp 数组的含义，这是解题的基础。常见的有一维/二维背包，有时需要增加维度。

3. 转移方程：考虑"选"与"不选"两种情况，这是动态规划的核心思想。

4. 初始化：特别是边界条件的处理，比如 dp[0] 的取值。

5. 遍历顺序：01背包通常需要倒序遍历，完全背包则是正序。

6. 空间优化：在面试中，从二维优化到一维往往能加分。

在实现时，我建议：

• 先写出基础版的二维DP，确保逻辑正确
• 再考虑空间优化
• 特别注意边界条件和特殊输入（如空数组、全0等情况）

动态规划需要大量练习才能掌握，建议从背包问题入手，逐步扩展到其他类型的DP问题。这三个题目都是很好的练习素材，建议反复琢磨其中的状态转移过程。