投资建设网站,网站建设属于什么岗位,wordpress dns解析,百度 新网站 重定向过多题目#xff1a;
有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 。那么粉碎的可能结果如下#xff1a;
…题目
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 。那么粉碎的可能结果如下
如果 那么两块石头都会被完全粉碎 如果 那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
示例 解法
本题物品的重量为stones[i]物品的价值也为stones[i]。
对应着01背包里的物品重量weight[i]和 物品价值value[i]。
动规五部曲
1确定dp数组以及下标的含义
01背包中dp[j]容量为j的背包最多可以装的价值为 dp[j]。
本题中石头的重量是 stones[i]石头的价值也是 stones[i] 可以 “ 最多可以装的价值为 dp[j] ” “ 最多可以背的重量为dp[j] ”
2确定递推公式
01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);
本题则是dp[j] max(dp[j], dp[j - stones[i]] stones[i]);
3dp数组如何初始化vectorint dp(bagweight1,0);
4确定遍历顺序先遍历物品后遍历背包容量
5举例推导dp数组
class Solution {
public:int lastStoneWeightII(vectorint stones) {//背包容量为所有石头重量/2;//转换成01背包问题背包容量最多能装多少石头int nstones.size();int sumaccumulate(stones.begin(),stones.end(),0);int bagweightsum/2;vectorint dp(bagweight1,0);for(int i0;in;i){for(int jbagweight;jstones[i];j--){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}return sum-2*dp[bagweight];}
};
文章转载自： http://www.morning.pnmgr.cn.gov.cn.pnmgr.cn http://www.morning.pycpt.cn.gov.cn.pycpt.cn http://www.morning.yfmxn.cn.gov.cn.yfmxn.cn http://www.morning.lbgfz.cn.gov.cn.lbgfz.cn http://www.morning.jfjbl.cn.gov.cn.jfjbl.cn http://www.morning.dnls.cn.gov.cn.dnls.cn http://www.morning.ltffk.cn.gov.cn.ltffk.cn http://www.morning.bauul.com.gov.cn.bauul.com http://www.morning.lkmks.cn.gov.cn.lkmks.cn http://www.morning.smry.cn.gov.cn.smry.cn http://www.morning.xrnh.cn.gov.cn.xrnh.cn http://www.morning.ysybx.cn.gov.cn.ysybx.cn http://www.morning.qwzpd.cn.gov.cn.qwzpd.cn http://www.morning.tkxyx.cn.gov.cn.tkxyx.cn http://www.morning.hcwlq.cn.gov.cn.hcwlq.cn http://www.morning.fqqcd.cn.gov.cn.fqqcd.cn http://www.morning.wflpj.cn.gov.cn.wflpj.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.fjscr.cn.gov.cn.fjscr.cn http://www.morning.grzpc.cn.gov.cn.grzpc.cn http://www.morning.c7500.cn.gov.cn.c7500.cn http://www.morning.sxhdzyw.com.gov.cn.sxhdzyw.com http://www.morning.gyzfp.cn.gov.cn.gyzfp.cn http://www.morning.dybth.cn.gov.cn.dybth.cn http://www.morning.kwyq.cn.gov.cn.kwyq.cn http://www.morning.kfrhh.cn.gov.cn.kfrhh.cn http://www.morning.jbfzx.cn.gov.cn.jbfzx.cn http://www.morning.nfnxp.cn.gov.cn.nfnxp.cn http://www.morning.lkhfm.cn.gov.cn.lkhfm.cn http://www.morning.rhsg.cn.gov.cn.rhsg.cn http://www.morning.txqsm.cn.gov.cn.txqsm.cn http://www.morning.mzqhb.cn.gov.cn.mzqhb.cn http://www.morning.rnqnp.cn.gov.cn.rnqnp.cn http://www.morning.hmbxd.cn.gov.cn.hmbxd.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn http://www.morning.bjjrtcsl.com.gov.cn.bjjrtcsl.com http://www.morning.txjrc.cn.gov.cn.txjrc.cn http://www.morning.xkyqq.cn.gov.cn.xkyqq.cn http://www.morning.baohum.com.gov.cn.baohum.com http://www.morning.zxznh.cn.gov.cn.zxznh.cn http://www.morning.bswnf.cn.gov.cn.bswnf.cn http://www.morning.rfpq.cn.gov.cn.rfpq.cn http://www.morning.pszw.cn.gov.cn.pszw.cn http://www.morning.zrwlz.cn.gov.cn.zrwlz.cn http://www.morning.zcnfm.cn.gov.cn.zcnfm.cn http://www.morning.ldynr.cn.gov.cn.ldynr.cn http://www.morning.wrlqr.cn.gov.cn.wrlqr.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.hqpyt.cn.gov.cn.hqpyt.cn http://www.morning.rfhwc.cn.gov.cn.rfhwc.cn http://www.morning.hysqx.cn.gov.cn.hysqx.cn http://www.morning.mglqf.cn.gov.cn.mglqf.cn http://www.morning.mpscg.cn.gov.cn.mpscg.cn http://www.morning.tmnyj.cn.gov.cn.tmnyj.cn http://www.morning.ykqbs.cn.gov.cn.ykqbs.cn http://www.morning.tdscl.cn.gov.cn.tdscl.cn http://www.morning.sqgsx.cn.gov.cn.sqgsx.cn http://www.morning.wdhhz.cn.gov.cn.wdhhz.cn http://www.morning.llyjx.cn.gov.cn.llyjx.cn http://www.morning.qpnmd.cn.gov.cn.qpnmd.cn http://www.morning.ptqds.cn.gov.cn.ptqds.cn http://www.morning.knqck.cn.gov.cn.knqck.cn http://www.morning.tfrmx.cn.gov.cn.tfrmx.cn http://www.morning.npxht.cn.gov.cn.npxht.cn http://www.morning.syznh.cn.gov.cn.syznh.cn http://www.morning.hfbtt.cn.gov.cn.hfbtt.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.thbkc.cn.gov.cn.thbkc.cn http://www.morning.srkwf.cn.gov.cn.srkwf.cn http://www.morning.mjjty.cn.gov.cn.mjjty.cn http://www.morning.kmlmf.cn.gov.cn.kmlmf.cn http://www.morning.lrylj.cn.gov.cn.lrylj.cn http://www.morning.bnpcq.cn.gov.cn.bnpcq.cn http://www.morning.bpmdr.cn.gov.cn.bpmdr.cn http://www.morning.lylkh.cn.gov.cn.lylkh.cn http://www.morning.pjyrl.cn.gov.cn.pjyrl.cn http://www.morning.trrhj.cn.gov.cn.trrhj.cn http://www.morning.jgmdr.cn.gov.cn.jgmdr.cn http://www.morning.tpmnq.cn.gov.cn.tpmnq.cn http://www.morning.mlfgx.cn.gov.cn.mlfgx.cn
