LeetCode(微博搜索)-20240203-1

本条微博地址 一听开开
怎么会有leetcode带刷视频这种讲不清楚并且信息传递效率极低的东西？ 本条微博地址 碎碎碎碎念·
感谢Leetcode 现在有两个鼠标垫啦 本条微博地址 小吃部主任
本来明天要和喜欢的女的出去玩 结果晚上她把我鸽了说要在家刷leetcode 我服了 本条微博地址 gitpush-force
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
记忆化搜索。观察数据范围就知道是一道记忆化搜索题。首先思考一种特殊情况，若数组两边值相等，当前玩家如何抉择？一定是知道后续所有可能选择一种最优，而两玩家的思路都是获得尽可能多的分，那么对于下一回合，当前玩家能做的就是选择让对手获得少的分。每回合有两种选择(左或右)，分别利用前缀和计算当前获得分数，减去做完选择后下一轮对手的最优选择，然后看两种选择哪一种能获得更多的分差。这里用memo[l][r]表示当前数组端点为l,r时的最大得分差，若其计算过直接返回。最终答案即为memo[0][n-1]。
国际站每日一题今日思路：
动态规划。观察到数据限制1e3，可以两重循环。记dp[i]数组为划分到第i位置时的最大和。这里我用的是从后向前计算，从前向后也可以。对于当前为位置，可以向后最多寻找k位连续的数；选择连续子数组的过程中计算最大值，当前位置的最大划分为dp[j]=max(dp[j], dp[i+1]+mx*(i-j+1)。j为当前位置，i为可以选择划分的位置，mx为(i,j)间最大的数。最终答案为dp[0]。
#每日一题# #LeetCode# #每天59秒拿下每日一题# 本条微博地址 熵x殇Entropy