制作网站的步骤域名,网站产品推广,网站备案完电信,台山市网站建设1.题目解析 题目来源 1049.最后一块石头的重量II——力扣 测试用例 2.算法原理 首先需要将该问题转化为0-1背包问题后再做分析 1.状态表示
根据数学中的知识我们知道将一个数字分为两个子数后求这两个子数的最小差值#xff0c;那么就要求这两个子数尽可能接近于原数字的一… 1.题目解析 题目来源 1049.最后一块石头的重量II——力扣 测试用例 2.算法原理 首先需要将该问题转化为0-1背包问题后再做分析 1.状态表示
根据数学中的知识我们知道将一个数字分为两个子数后求这两个子数的最小差值那么就要求这两个子数尽可能接近于原数字的一半那么就一定会出现一大一小两个数或者两个相等的数这时就需要去找总和不大于原数字一半的数字然后找到另一半用另一半减去找到的数字即可所以需要二维dp表第一个下标表示已经寻找数字的区间第二个下标表示此时已寻找并选择数字的总和即dp[i][j]在[1,i]区间选择的数字总和不大于(小于或等于) j 的总和大小
2.状态转移方程
首先依旧是背包问题的思路对最后一个位置进行分类讨论首先判断当第i个位置不会选取此时就找到dp[i-1][j]判断此时的方法数然后判断选取第i个位置的数此时就需要寻找到dp[i-1][j-nums[i-1]]这个位置的dp表的值然后加到总方法数中去当然需要判断jnums[i-1] 3.初始化 4.填表顺序
从上到下每一行从左到右
5.返回值
返回两个子数相减也就是sum - dp[n][aim]*2sum - dp[n][aim] 与 dp[n][aim]两个子数 3.实战代码 class Solution {
public:int lastStoneWeightII(vectorint stones){int sum 0;for(auto e : stones){sum e;} int aim sum / 2;int n stones.size();vectorvectorint dp(n1,vectorint(aim1));for(int i 1;i n;i){for(int j 0;j aim;j){dp[i][j] dp[i-1][j];if(j stones[i-1]){dp[i][j] max(dp[i][j],dp[i-1][j - stones[i-1]] stones[i-1]);}}}return sum - dp[n][aim] - dp[n][aim];}
}; 代码解析 空间优化
