赞
踩
小明和朋友玩跳格子游戏,有 n
个连续格子组成的圆圈,每个格子有不同的分数,小朋友可以选择从任意格子起跳,但是不能跳连续的格子,不能回头跳,也不能超过一圈;
给定一个代表每个格子得分的非负整数数组,计算能够得到的最高分数。
给定一个数例,第一个格子和最后一个格子首尾相连,如: 2 3 2
。
输出能够得到的最高分,如: 3
。
1 <= nums.length <= 100
0 <= nums[i] <= 1000
2 3 2
3
只能跳 3
这个格子,因为第一个格子和第三个格子收尾相连
1 2 3 1
4
选择第一个和第三个格子,1 + 3 = 4
注意,本题和LC213. 打家劫舍II完全一致。
# 题目:2023B-跳格子(2) # 分值:100 # 作者:闭着眼睛学数理化 # 算法:动态规划 # 代码看不懂的地方,请直接在群上提问 # 用于单次动态规划的函数 def myRob(nums): # 获取格子总数 n = len(nums) # 创建一个数组value来存放前n个格子可以获得的最大分数 value = [0] * (n + 1) # 前0个格子无法跳跃,分数为0 value[0] = 0 # 前1个格子只有一个格子可跳跃,分数为该格子的分数 value[1] = nums[0] # 从i = 2到i = n,value中的结果由前i-2和i-1共同决定 for i in range(2, n + 1): # 转移方程:value[i]等于value[i-1]和value[i-2]+nums[i-1]中的较大值 value[i] = max(value[i - 1], value[i - 2] + nums[i - 1]) # 返回value的最后一个值 return value[n] # 输入数组 nums = list(map(int, input().split())) # 获取格子总数 n = len(nums) # 如果数组为空,输出0 if n == 0: print(0) # 如果数组只有一个元素,输出该元素的分数 elif n == 1: print(nums[0]) # 如果数组不止一个元素,则分别考虑不选择第一个格子、不选择最后一个格子的情况 elif: # 不选择第一个格子 nums_except_first_room = nums[1:] # 不选择最后一个格子 nums_except_last_room = nums[:-1] # 从这两个选择中挑选出最大值,并输出 print(max(myRob(nums_except_first_room), myRob(nums_except_last_room)))
时间复杂度:O(N)
。单次动态规划过程,仅需一次遍历数组nums
。需要做两次独立的动态规划过程,O(2N) = O(N)
空间复杂度:O(N)
。dp数组所占据的空间。
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336
了解更多
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。