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;
}
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OnT6fammwaFOSOcWl0PXBLpg0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
