深度剖析：动态规划的分类及实例

如你所知动态规划可以根据问题特性分为多种类型以下是几种经典问题类型及对应的实例。背包问题背包问题是一种资源类问题涉及在给定约束条件下如何最大化目标值。常见的是 0-1 背包、完全背包、多重背包。0-1 背包问题每个物品只选择一次典型题目分割等和子集题目描述给定一个只包含正整数的数组判断是否可以将它分割成两个子集使得两个子集的和相等。解题思路这个题目可以换一种思路给定一个只包含正整数的非空数组判断是否可以从数组中选出一些数字使得这些数字的和等于整个数组的元素和的一半。因此这个问题可以转换成0−1 背包问题。这道题与传统的0−1 背包问题的区别在于传统的0−1 背包问题要求选取的物品的重量之和不能超过背包的总容量这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。在使用动态规划求解之前首先需要进行以下判断1. 根据数组的长度 n 判断数组是否可以被划分。如果 n2则不可能将数组分割成元素和相等的两个子集因此直接返回 false。2. 为了能实现目标值为 target/2如果 target 是奇数直接返回 false。创建动态数组 dpdp[j] 表示能否从数组的前几个元素中选出一个子集使得子集的和等于 j。dp[j] 是一个布尔值初始状态是 dp[0] 为 true,因为不选任何元素和为 0 是可行的。对于每个 nums[i]我们有两种选择如果不选 nums[i]子集的和仍然是 j所以 dp[j] dp[j]如果选 nums[i]在选这个数之前子集的和仍然是 j-nums[i]。如果能从之前的元素中找到和为 j-nums[i]那么 dp[j] dp[j-nums[i]] || dp[j]。其中dp[j] 表示上一次的值即以前就可以组成和为 j 的子集不依赖 nums[i]那么此时依然可以组成和为 j。代码如下bool canPartition(vectorint nums) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum % 2 ! 0) return false; int target sum / 2; vectorbool dp(target 1, false); dp[0] true; // 和为 0 总是可以实现的 for (int num : nums) { for (int j target; j num; --j) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; }时间复杂度O(n*target)空间复杂度O(target)好了本篇文章的介绍到这里就结束了希望对大家的学习有所帮助哦