没有新消息
更多内容
0 条评论
暂无评论,快来写下您的评论
问题来自于
福大大
#福大大架构师每日一题#2023-11-25:用go语言,给定一个数组arr,长度为n,表示n个格子的分数,并且这些格子首尾
2023-11-25:用go语言,给定一个数组arr,长度为n,表示n个格子的分数,并且这些格子首尾相连, 孩子不能选相邻的格子,不能回头选,不能选超过一圈, 但是孩子可以决定从任何位置开始选,也可以什么都不选。 返回孩子能获得的最大分值。 1 <= n <= 10^6, 0 <= arr[
2620
阅读
3
回答
@2025 职Q 智联招聘
合作商务邮箱:sbyh@zhaopin.com.cn
友情链接
HR圈内招聘/ 同道问答/ 人资知识社区
51社保/ X职场/ HR Bar/ 中人网/ 研招网
京ICP备17067871号 合字B2-20210134
京公网安备 11010502030147号
人力资源许可证:1101052003273号
网上有害信息举报专区
违法不良信息举报电话:400-885-9898
关爱未成年举报热线:400-885-9898-7
朝阳区人力资源与社会保障局 监督电话: 57596212,65090445
#福大大架构师每日一题#2023-11-25:用go语言,给定一个数组arr,长度为n,表示n个格子的分数,并且这些格子首尾
这是一个动态规划问题,可以使用动态规划来解决。 首先,我们可以定义一个二维数组dp,其中dp[i][j]表示从第i个格子开始,选取j个格子的最大分值。 然后,我们可以根据题目的要求,得到状态转移方程: dp[i][j] = max(dp[i-2][j-1], dp[i-1][j-1]) + arr[i] 其中,dp[i-2][j-1]表示选取第i-2个格子,不选取第i-1个格子,dp[i-1][j-1]表示选取第i-1个格子,不选取第i个格子。 最后,我们只需要遍历数组arr,计算出dp数组的每个元素,最终返回dp[n-1][k],其中k表示孩子最多能选取的格子数量。 下面是代码实现: ```go func maxScore(arr []int) int { n := len(arr) k := n - 1 // 孩子最多能选取的格子数量 dp := make([][]int, n) // 动态规划数组 for i := range dp { dp[i] = make([]int, k+1) } dp[0][0] = arr[0] for i := 1; i < n; i++ { for j := 1; j <= k; j++ { dp[i][j] = max(dp[i-2][j-1], dp[i-1][j-1]) + arr[i] } } return dp[n-1][k] } func max(a, b int) int { if a > b { return a } return b } ``` 时间复杂度为O(n*k),其中n为数组的长度,k为孩子最多能选取的格子数量。空间复杂度为O(n*k)。