(问答题)
高兴万圣节去抢劫一条街上的糖果店,为了不触发报警,他不能抢劫连续的2家店(可以间隔1家,也可以间隔多家糖果店),设计程序计算一下高兴万圣节最多能抢到多少糖果。(使用递归方法)
样例格式:
输入:
第一行:有多少糖果店n,n不超过30
第二行:每家糖果店的糖果数量
输出:
能抢到最多糖果的总数
具体样例:
输入:
3

C++请教,请教,请教。递归和不用递归方法
- 写回答
- 好问题 0 提建议
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- 真相重于对错 2022-01-23 11:44关注
不使用递归可以使用动态规划,每个商店有俩个状态,抢或者不抢,用一个数组表示达到每个商店所获得最大糖果值
如果不抢,那就是上一个商店的值,如果抢则是前两个商店的最大值+本商店的糖果,比较二者的大小确定抢还是不抢。
这个算法也可以写成递归伪代码如下int qiangjie(vector<int>nums,int len) { if(len==1) return nums[0]; if(len==2) { reutrn max(nums[0],mums[1]) } else{ return max(qiangjie(len-1),qiangjie(len-2)+nums[len]); } }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 2无用