Abstract：#动态规划#区间DP#博弈
1. 题目
- 题目：LeetCode 486. 预测赢家
- 核心思路：两人轮流从数组两端取数，最终分数高者赢。定义
f(l, r)表示在子数组nums[l…r]中当前先手玩家能获得的最大分数。转移时，若取左端nums[l]，则对手会在[l+1, r]中成为先手，且对手会采取最优策略使当前玩家后续得分最小，所以当前玩家总得分为nums[l] + min(f(l+1, r-1), f(l+2, r))；取右端同理。最终先手得分first = f(0, n-1)，后手得分second = sum - first，若first >= second则先手赢。 - 复杂度：时间复杂度O ( n 2 ) O(n²)O(n2)，空间复杂度O ( n 2 ) O(n²)O(n2)（可空间压缩至O ( n ) O(n)O(n)）。
2. 代码
classSolution{public:intf(vector<int>&nums,vector<vector<int>>&dp,intl,intr){if(dp[l][r]!=-1)returndp[l][r];intn=nums.size(),ans;if(l==r)ans=nums[l];elseif(l==r-1)ans=max(nums[l],nums[r]);else{intp1=nums[l]+min(f(nums,dp,l+1,r-1),f(nums,dp,l+2,r));intp2=nums[r]+min(f(nums,dp,l+1,r-1),f(nums,dp,l,r-2));ans=max(p1,p2);}dp[l][r]=ans;returnans;}boolpredictTheWinner(vector<int>&nums){intsum=0;for(autonum:nums){sum+=num;}vector<vector<int>>dp(25,vector<int>(25,-1));intfirst=f(nums,dp,0,nums.size()-1);intsecond=sum-first;returnfirst>=second?true:false;}};3. 心得
区间DP思想：将大范围问题拆解成若干小范围上的问题求解，这里的小范围问题是大范围问题的重叠子问题。这种拆解方法总是基于分情况讨论的思想而得出的，就区间DP而言有两种讨论思路：一是基于两侧端点的可能性展开（如本题无论是从情景还是从分析过程，都是在左右两侧端点操作的）；二是基于范围中的划分点展开（具体题目见明日再学）。
博弈DP中的min理解：当前玩家取走一个数后，对手在剩余区间成为先手，且对手会最大化自己的分数，等价于让当前玩家在后续中得到尽可能小的分数。因此转移时要取min，而不是max。
4. 相关题目
- LeetCode 1312. 让字符串成为回文串的最少插入次数
