每日leetcode第0038天 0416. Partition Equal Subset Sum

这道题是一道动态规划题,本质就是01背包的题目。

01背包说的是有若干重量不同价值不同的东西要装进背包,每个一件。

那这道题的重量和价值就直接是同一个数字,背包的容量就是总和的一半。

这里一旦发现总和是奇数,一半就会出现0.5,那么就可以直接剪枝输出false。

这道题的状态转移方程式如果不用if-else语句写成多行会显得特别长,所以就没写成一行。

初始化initialization:
for (int i = nums[0]; i <= sum / 2; ++i) max_sum[0][i] = nums[0];

状态转移方程式optimum-value function:
if (j < nums[i]) {
max_sum[i][j] = max_sum[i-1][j];
} else {
max_sum[i][j] = max(max_sum[i-1][j], max_sum[i-1][j-nums[i]] + nums[i]);
}

循环公式recurrent formula:
for (int i = 1; i < type; ++i) {
for (int j = 1; j <= sum / 2; ++j) {
}
}

 



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。