发动态

没有新消息

更多内容

#福大大架构师每日一题#2023-11-25:用go语言,给定一个数组arr,长度为n,表示n个格子的分数,并且这些格子首尾

智小Q AI个人助理

这是一个动态规划问题,可以使用动态规划来解决。 首先,我们可以定义一个二维数组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)。

13 赞+1
0
评论

0 条评论

暂无评论,快来写下您的评论

推荐阅读

#福大大架构师每日一题#2021-04-07:给定一个非负数组arr,长度为N,那么有N-1种方案可以把arr切成左右两

2回答   3201阅读

#福大大架构师每日一题#2021-04-25:给定一个数组arr,和一个正数M,返回在arr的子数组在长度不超过M的情况下,

0回答   1854阅读

#福大大架构师每日一题#2021-12-26:给定一个长度为n的数组arr,求有多少个子数组满足 : 子数组两端的值,是这

0回答   1326阅读

#福大大架构师每日一题#2022-01-12:给定一个正数数组arr,长度为n,下标0~n-1, arr中的0、n-1位置不

0回答   1491阅读

#福大大架构师每日一题#2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格

3回答   2884阅读

#福大大架构师每日一题#2023-03-02:给定一个数组arr,长度为n, 任意相邻的两个数里面至少要有一个被选出来,组成

2回答   844阅读

#福大大架构师每日一题#2023-08-30:用go语言编写。两个魔法卷轴问题。 给定一个数组arr,其中可能有正、负、0,

2回答   1155阅读

#福大大架构师每日一题#2023-11-11:用go语言,字符串哈希+二分的例题。 给定长为 n 的源串 s,以及长度为 m

4回答   1584阅读

#福大大架构师每日一题#2023-12-20:用go语言,给定一个数组arr,长度为n,在其中要选两个不相交的子数组。 两个

3回答   2039阅读
正在发声