2023-11-25：用go语言，给定一个数组arr，长度为n，表示n个格子的分数，并且这些格子首尾相连， 孩子不能选相邻的格子

2023-11-25：用go语言，给定一个数组arr，长度为n，表示n个格子的分数，并且这些格子首尾相连，

孩子不能选相邻的格子，不能回头选，不能选超过一圈，

但是孩子可以决定从任何位置开始选，也可以什么都不选。

返回孩子能获得的最大分值。

1

0

来自华为od。

来自左程云。

答案2023-11-25：

go和c++的代码用灵捷3.5编写，感觉有点抽风了，生成的代码需要修改才能运行。

大体过程如下：

1.暴力方法（max1函数）

这种方法是一种递归的方式，通过尝试所有可能的组合来找到最大分值。

• 定义max1函数，接受一个长度为n的数组arr作为参数。

• 若arr的长度为1，直接返回arr[]作为结果。

• 否则，调用process函数，传入arr、起始索引和一个长度为n的布尔类型数组path（用于记录选择的路径）。

• 在process函数中，先检查是否已经遍历到数组末尾，若是，则判断首尾是否相连，如果是则返回最小整数值math.MinInt32，否则遍历整个数组检查相邻格子是否被选中，如果有返回最小整数值。

• 初始化ans为，遍历数组，如果path[j]为true，则将arr[j]加到ans上。

• 返回ans作为结果。

2.记忆化搜索（max2函数）

这种方法使用动态规划的思想，借助一个二维数组dp来存储已计算的结果，以减少重复计算。

• 定义max2函数，接受一个长度为n的数组arr作为参数。

• 若arr的长度为1，直接返回arr[]作为结果。

• 否则，初始化n为arr的长度，并创建一个二维数组dp，大小为[n][4]，并将其所有元素设置为最小整数值math.MinInt32。

• 初始化ans为arr[]加上调用process2函数的结果，传入arr、起始索引1、、和dp。

• 将ans更新为ans与调用process2函数，传入arr、起始索引1、、和dp的结果中的较大值。

• 返回ans作为结果。

3.正式方法（max3函数）

这种方法是一种严格位置依赖的动态规划方法，同时使用空间压缩技巧，减少额外空间的使用。

• 定义max3函数，接受一个长度为n的数组arr作为参数。

• 若arr的长度为1，直接返回arr[]作为结果。

• 否则，初始化n为arr的长度，并创建两个大小为4的一维数组next和cur，用于保存计算过程中的结果。

• 将next[]初始化为arr[n-1]的最大值和的较大值（即取和arr[n-1]的较大值）。

• 从n-2开始向前遍历数组arr，进行动态规划计算。

• 在每次遍历中，使用三重嵌套循环，遍历pre和end，计算cur[(pre

• 更新next数组的值为cur数组的值。

• 最终，返回arr[]+next[3]和next[]中的较大值作为结果。

总结时间复杂度和空间复杂度：

• 第一种暴力方法的时间复杂度为O(2^n)，空间复杂度为O(n)。

• 第二种记忆化搜索的时间复杂度为O(n)，空间复杂度为O(n)。

• 第三种正式方法的时间复杂度为O(n)，空间复杂度为O(1)。

go完整代码如下：

package main

import (

"fmt"

"math"

"math/rand"

"time"

)

// 暴力方法

func max1(arr []int) int {

if len(arr) == 1 {

return arr[0]

}

return process(arr, 0, make([]bool, len(arr)))

}

func process(arr []int, i int, path []bool) int {

if i == len(arr) {

if path[0] && path[len(arr)-1] {

return math.MinInt32

}

for j := 1; j 

if path[j-1] && path[j] {

return math.MinInt32

}

}

ans := 0

for j := 0; j 

if path[j] {

ans += arr[j]

}

}

return ans

} else {

path[i] = true

ans1 := process(arr, i+1, path)

path[i] = false

ans2 := process(arr, i+1, path)

return int(math.Max(float64(ans1), float64(ans2)))

}

}

// 时间复杂度O(N)，记忆化搜索

func max2(arr []int) int {

if len(arr) == 1 {

return arr[0]

}

n := len(arr)

dp := make([][]int, n)

for i := 0; i 

dp[i] = make([]int, 4)

for j := 0; j 

dp[i][j] = math.MinInt32

}

}

ans := arr[0] + process2(arr, 1, 1, 1, dp)

ans = int(math.Max(float64(ans), float64(process2(arr, 1, 0, 0, dp))))

return ans

}

func process2(arr []int, i, pre, end int, dp [][]int) int {

if i == len(arr)-1 {

returnValue := 0

if pre == 1 || end == 1 {

return returnValue

} else {

return int(math.Max(float64(returnValue), float64(arr[i])))

}

} else {

if dp[i][(pre

return dp[i][(pre

}

p1 := process2(arr, i+1, 0, end, dp)

p2 := math.MinInt32

if pre != 1 {

p2 = arr[i] + process2(arr, i+1, 1, end, dp)

}

ans := int(math.Max(float64(p1), float64(p2)))

dp[i][(pre

return ans

}

}

// 正式方法

// 严格位置依赖的动态规划 + 空间压缩

// 时间复杂度O(N)

func max3(arr []int) int {

if len(arr) == 1 {

return arr[0]

}

n := len(arr)

next := make([]int, 4)

cur := make([]int, 4)

next[0] = int(math.Max(0, float64(arr[n-1])))

for i := n - 2; i >= 1; i-- {

for pre := 0; pre 

for end := 0; end 

cur[(pre

if pre != 1 {

cur[(pre

}

}

}

next[0] = cur[0]

next[1] = cur[1]

next[2] = cur[2]

next[3] = cur[3]

}

return int(math.Max(float64(arr[0]+next[3]), float64(next[0])))

}

// 为了测试

func randomArray(n, v int) []int {

arr := make([]int, n)

for i := 0; i 

arr[i] = int(math.Floor(float64(v) * rand.Float64()))

}

return arr

}

func main() {

N := 16

V := 100

testTimes := 500

fmt.Println("测试开始")

rand.Seed(time.Now().UnixMilli())

for i := 0; i 

n := rand.Intn(N) + 1

arr := randomArray(n, V)

ans1 := max1(arr)

ans2 := max2(arr)

ans3 := max3(arr)

if ans1 != ans2 || ans1 != ans3 {

fmt.Println("出错了！", i)

return

}

}

fmt.Println("测试结束")

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

#include 

#include 

#include 

using namespace std;

int process(vector& arr, int i, vector& path);

int max1(vector& arr) {

if (arr.size() == 1) {

return arr[0];

}

vector a = vector(arr.size(), false);

return process(arr,0 , a);

}

int process(vector& arr, int i, vector& path) {

if (i == arr.size()) {

if (path[0] && path[arr.size() - 1]) {

return INT32_MIN;

}

for (int j = 1; j 

if (path[j - 1] && path[j]) {

return INT32_MIN;

}

}

int ans = 0;

for (int j = 0; j 

if (path[j]) {

ans += arr[j];

}

}

return ans;

}

else {

path[i] = true;

int ans1 = process(arr, i + 1, path);

path[i] = false;

int ans2 = process(arr, i + 1, path);

return max(ans1, ans2);

}

}

int process2(vector& arr, int i, int pre, int end, vector& dp);

int max2(vector& arr) {

if (arr.size() == 1) {

return arr[0];

}

int n = arr.size();

vector dp(n, vector(4, INT32_MIN));

int ans = arr[0] + process2(arr, 1, 1, 1, dp);

ans = max(ans, process2(arr, 1,0 ,0 , dp));

return ans;

}

int process2(vector& arr, int i, int pre, int end, vector& dp) {

if (i == arr.size() - 1) {

int returnValue =0 ;

if (pre == 1 || end == 1) {

return returnValue;

}

else {

return max(returnValue, arr[i]);

}

}

else {

if (dp[i][(pre 

return dp[i][(pre 

}

int p1 = process2(arr, i + 1,0 , end, dp);

int p2 = INT32_MIN;

if (pre != 1) {

p2 = arr[i] + process2(arr, i + 1, 1, end, dp);

}

int ans = max(p1, p2);

dp[i][(pre 

return ans;

}

}

int max3(vector& arr) {

if (arr.size() == 1) {

return arr[0];

}

int n = arr.size();

vector next(4);

vector cur(4);

next[0] = max(0, arr[n - 1]);

for (int i = n - 2; i >= 1; i--) {

for (int pre = 0; pre 

for (int end = 0; end 

cur[(pre 

if (pre != 1) {

cur[(pre 

}

}

}

next[0] = cur[0];

next[1] = cur[1];

next[2] = cur[2];

next[3] = cur[3];

}

return max(arr[0] + next[3], next[0]);

}

vector randomArray(int n, int v) {

vector arr(n);

srand(time(NULL));

for (int i = 0; i 

arr[i] = floor(v * ((double)rand() / RAND_MAX));

}

return arr;

}

int main() {

int N = 16;

int V = 100;

int testTimes = 500;

cout 

for (int i = 0; i 

int n = rand() % N + 1;

vector arr = randomArray(n, V);

int ans1 = max1(arr);

int ans2 = max2(arr);

int ans3 = max3(arr);

if (ans1 != ans2 || ans1 != ans3) {

cout 

return 0;

}

}

cout 

return 0;

}

在这里插入图片描述