没有新消息
0 条评论
暂无评论,快来写下您的评论
问题来自于
福大大
北京/西昌学院/研发工程师
#福大大架构师每日一题#2023-11-25:用go语言,给定一个数组arr,长度为n,表示n个格子的分数,并且这些格子首尾
2023-11-25:用go语言,给定一个数组arr,长度为n,表示n个格子的分数,并且这些格子首尾相连, 孩子不能选相邻的格子,不能回头选,不能选超过一圈, 但是孩子可以决定从任何位置开始选,也可以什么都不选。 返回孩子能获得的最大分值。 1 <= n <= 10^6, 0 <= arr[
1881
阅读
3
回答
#福大大架构师每日一题#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)。