(B卷,200分)- 跳格子2（Java & JS & Python & C）

题目描述

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

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

输入描述

给定一个数例，第一个格子和最后一个格子首尾相连，如: 2 3 2

输出描述

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

备注

• 1 ≤ nums.length ≤ 100
• 1 ≤ nums[i] ≤ 1000

用例

题目解析

本题是的换皮题

解析请看链接博客。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const nums = line.split(" ").map(Number);
  console.log(getResult(nums));
});

function getResult(nums) {
  if (nums.length == 1) return nums[0];

  return Math.max(
    stealMaxMoney(nums.slice(0, -1)),
    stealMaxMoney(nums.slice(1))
  );
}

function stealMaxMoney(nums) {
  const n = nums.length;

  const dp = new Array(n);

  if (n >= 1) dp[0] = nums[0];
  if (n >= 2) dp[1] = Math.max(nums[0], nums[1]);

  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }

  return dp[n - 1];
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    System.out.println(getResult(nums));
  }

  public static int getResult(int[] nums) {
    if (nums.length == 1) return nums[0];

    return Math.max(
        stealMaxMoney(Arrays.copyOfRange(nums, 0, nums.length - 1)),
        stealMaxMoney(Arrays.copyOfRange(nums, 1, nums.length)));
  }

  public static int stealMaxMoney(int[] nums) {
    int n = nums.length;

    int[] dp = new int[n];

    if (n >= 1) dp[0] = nums[0];
    if (n >= 2) dp[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < n; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[n - 1];
  }
}

Python算法源码

# 输入获取
nums = list(map(int, input().split()))


def stealMaxMoney(nums):
    n = len(nums)

    dp = [0] * n

    if n >= 1:
        dp[0] = nums[0]

    if n >= 2:
        dp[1] = max(nums[0], nums[1])

    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[n - 1]


# 算法入口
def getResult():
    if len(nums) == 1:
        return nums[0]

    return max(stealMaxMoney(nums[:-1]), stealMaxMoney(nums[1:]))


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX_SIZE 100

#define MAX(a,b) a > b ? a : b

int getResult(int* nums, int nums_size);
int stealMaxMoney(int* nums, int nums_size);

int main()
{
int nums[MAX_SIZE];
int nums_size = 0;
while(scanf("%d", &nums[nums_size++])) {
if(getchar() != ' ') break;
}

printf("%dn", getResult(nums, nums_size));

return 0;
}

int getResult(int* nums, int nums_size)
{
if(nums_size == 1) {
return nums[0];
}

return MAX(stealMaxMoney(nums, nums_size - 1), stealMaxMoney(nums + 1, nums_size - 1));
}

int stealMaxMoney(int* nums, int nums_size)
{
int dp[MAX_SIZE] = {0};

if(nums_size >= 1) {
dp[0] = nums[0];
}

if(nums_size >= 2) {
dp[1] = MAX(nums[0], nums[1]);
}

for(int i=2; i<nums_size; i++) {
dp[i] = MAX(dp[i-1], dp[i-2] + nums[i]);
}

return dp[nums_size-1];
}