一笑而过2222
2024-10-12 19:35 中山大学 测试工程师
关注
1. 求最大公约数的辅助函数 gcd(a, b) ：
- 使用辗转相除法来计算两个数的最大公约数。通过不断地将较大数变为较小数，较小数变为两数相除的余数，直到余数为 0，此时较大数就是最大公约数。
2. 计算最大得分的函数 max_score(nums, k) ：
- 首先确定问题的规模和状态表示：
- n 表示输入序列 nums 的长度。
- 创建一个二维列表 dp ，其中 dp[i][j] 表示前 i 个元素分成 j 个部分的最大得分。
- 然后进行状态转移：
- 对于每个 i 从 1 到 n （遍历整个序列）：
- 对于每个 j 从 1 到 min(i, k) （确保部分数不超过元素个数且不超过给定的要分成的部分数 k ）：
- 通过遍历不同的分割点 l 从 j - 1 到 i （确定当前部分的边界），计算当前状态 dp[i][j] 。
- 计算方式是取当前状态和前 l 个元素分成 j - 1 个部分的得分加上从 l 到 i 这部分的最大公约数中的较大值。这里的最大公约数通过调用 gcd(*nums[l:i]) 来计算，表示从 l 到 i 这个子序列中所有元素的最大公约数。
- 最后返回结果：
- dp[n][k] 即为前 n 个元素分成 k 个部分的最大得分。
查看原帖
2 评论
相关推荐
查看18道真题和解析 
投递京东等公司9个岗位 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 2025年终总结 #
148967次浏览 2533人参与
# 秋招落幕，你是He or Be #
3407次浏览 76人参与
# 应届生进小公司有什么影响吗 #
109174次浏览 1116人参与
# 比亚迪工作体验 #
70299次浏览 254人参与
# 你面试体验感最差/最好的公司 #
3333次浏览 57人参与
# 工作中听到最受打击的一句话 #
2701次浏览 62人参与
# 大厂VS公务员你怎么选 #
71454次浏览 660人参与
# 重来一次，你会对开始求职的自己说 #
3144次浏览 72人参与
# 一人说一个提前实习的好处 #
3661次浏览 75人参与
# 团建是“福利”还是是 “渡劫” #
4171次浏览 112人参与
# 实习没事做是福还是祸？ #
8609次浏览 137人参与
# 如何排解工作中的焦虑 #
244119次浏览 2241人参与
# 从顶到拉给所有面过的公司评分 #
144841次浏览 518人参与
# 今年你最想重开的一场面试是？ #
1503次浏览 26人参与
# 你小心翼翼的闯过多大的祸？ #
7153次浏览 109人参与
# 联影求职进展汇总 #
123877次浏览 781人参与
# OPPO求职进展汇总 #
755980次浏览 5390人参与
# 互联网公司爆料 #
158631次浏览 724人参与
# 产品实习，你更倾向大公司or小公司 #
189154次浏览 2053人参与
# 秋招结束之后的日子 #
113938次浏览 1039人参与