华为秋招笔试真题解析

五分钟学算法

发布于 2023-09-24 20:09:21

2730

发布于 2023-09-24 20:09:21

文章被收录于专栏：五分钟学算法五分钟学算法

大家好，我是吴师兄，关注我，每天更新大厂最新笔试题解析。

题目描述

小明和朋友玩跳格子游戏，有 n 个连续格子，每个格子有不同的分数，小朋友可以选择以任意格子起跳，但是不能跳连续的格子，也不能回头跳；

给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数

输入描述

给定一个数列，如: 1`` ``2 3 1

输出描述

输出能够得到的最高分，如: 4

备注

1 ≤ nums.length ≤ 100
0 <= nums[i] <= 1000

示例一

输入

1 2 3 1

输出

说明

选择跳第一个格子和第三个格子

示例二

输入

2 7 9 3 1

输出

说明

2`` ``+`` ``9`` ``+`` ``1`` ``=`` ``12

解题思路

注意，本题和LC198. 打家劫舍完全一致。

代码



# 输入分数数组
nums = list(map(int, input().split()))
# 获得格子数
n = len(nums)
# 如果长度为1，那么直接输出nums[0]
if n == 1:
    print(nums[0])
# 否则，进行dp过程
else:
    # 初始化长度为n的dp数组
    # dp[i]表示，考虑第i个格子时，能获得的最高分数
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    # 遍历剩余所有格子，
    # 动态转移方程为dp[i] = max(dp[i-1], nums[i] + dp[i-2])
    # 表示考虑dp[i]时，
    # 可以选择其前一个位置dp[i-1]的分数
    # 也可以选择其前两个位置dp[i-2]的分数加上nums[i]的分数
    for i in range(2, n):
        dp[i] = max(dp[i-1], nums[i] + dp[i-2])
    print(dp[-1])