当前位置：首页 > news >正文

数据结构与算法：区间dp

news 来源：原创 2025/8/20 14:06:15

前言

区间dp也是动态规划里很重要的一部分。

一、内容

区间dp的根本原理就是把大范围问题分解成若干小范围的问题去求解。一般来讲，常见的用法有对于两侧端点去展开可能性和对于范围上的划分点去展开可能性。

二、题目

1.让字符串成为回文串的最少插入次数

class Solution {
public:int minInsertions(string s) {//return recursion(0,s.length()-1,s);// vector<vector<int>>dp(s.length(),vector<int>(s.length(),-1));// return ms(0,s.length()-1,s,dp);// return DP(s);return optimized_dp(s);}//递归尝试 -> 超时int recursion(int i,int j,string &s){if(i==j){return 0;}if(i+1==j){return s[i]==s[j]?0:1;}if(s[i]==s[j]){return recursion(i+1,j-1,s);}else{return min(recursion(i+1,j,s),recursion(i,j-1,s))+1;}}//记忆化搜索int ms(int i,int j,string &s,vector<vector<int>>&dp){if(i==j){return 0;}if(i+1==j){return s[i]==s[j]?0:1;}if(dp[i][j]!=-1){return dp[i][j];}if(s[i]==s[j]){dp[i][j]=ms(i+1,j-1,s,dp);return dp[i][j];}else{dp[i][j]=min(ms(i+1,j,s,dp),ms(i,j-1,s,dp))+1;return dp[i][j];} }//动态规划int DP(string &s){int n=s.length();vector<vector<int>>dp(n,vector<int>(n));//初始化for(int i=0;i<n-1;i++){dp[i][i+1]=s[i]==s[i+1]?0:1;}for(int i=n-3;i>=0;i--){for(int j=i+2;j<n;j++){if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1];}else{dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;}}}return dp[0][n-1];}//空间压缩int optimized_dp(string &s){int n=s.length();//特例if(n<2){return 0;}vector<int>dp(n);dp[n-1]=s[n-2]==s[n-1]?0:1;for(int i=n-3,leftDown,tmp;i>=0;i--){leftDown=dp[i+1];dp[i+1]=s[i]==s[i+1]?0:1;for(int j=i+2;j<n;j++){tmp=dp[j];if(s[i]==s[j]){dp[j]=leftDown;}else{dp[j]=min(dp[j],dp[j-1])+1;}leftDown=tmp;}}return dp[n-1];}
};

这个题就是区间dp的第一个用法，就是去两端点展开可能性。能想到区间dp从两端展开就是因为要求是回文串。

首先还是从递归尝试入手，basecase就是当两端指针来到同一个字符时，那自己就能构成回文串，所以返回0；如果两指针相邻，那如果两字符相同就是0，不同就是1，即需要插入一次。之后就讨论当前字符对没对上，对上了就直接去之后递归；没对上就讨论插入左侧和右侧两种情况。

记忆化搜索直接挂个dp表即可。

动态规划直接观察严格位置依赖即可，那就是左下、左和下。

空间压缩时因为依赖左下的格子，所以每次要用一个leftDown记录左下。

2.预测赢家

class Solution {
public:bool predictTheWinner(vector<int>& nums) {int n=nums.size();int sum=0;for(int num:nums){sum+=num;}int first;// first=recursion(0,n-1,nums);// vector<vector<int>>dp(n,vector<int>(n,-1));// first=MS(0,n-1,nums,dp);first=DP(nums);int second=sum-first;return first>=second;}//递归尝试int recursion(int l,int r,vector<int>&nums){if(l==r){return nums[l];}if(l+1==r){return max(nums[l],nums[r]);}int p1=nums[l]+min(recursion(l+2,r,nums),recursion(l+1,r-1,nums));int p2=nums[r]+min(recursion(l,r-2,nums),recursion(l+1,r-1,nums));return max(p1,p2);}//记忆化搜索int MS(int l,int r,vector<int>&nums,vector<vector<int>>&dp){if(l==r){return nums[l];}if(l+1==r){return max(nums[l],nums[r]);}if(dp[l][r]!=-1){return dp[l][r];}int p1=nums[l]+min(MS(l+2,r,nums,dp),MS(l+1,r-1,nums,dp));int p2=nums[r]+min(MS(l,r-2,nums,dp),MS(l+1,r-1,nums,dp));dp[l][r]=max(p1,p2);return dp[l][r];}//动态规划int DP(vector<int>&nums){int n=nums.size();vector<vector<int>>dp(n,vector<int>(n));//初始化for(int i=0;i<n;i++){dp[i][i]=nums[i];if(i+1<n){dp[i][i+1]=max(nums[i],nums[i+1]);}}for(int i=n-3;i>=0;i--){for(int j=i+2;j<n;j++){int p1=nums[i]+min(dp[i+2][j],dp[i+1][j-1]);int p2=nums[j]+min(dp[i][j-2],dp[i+1][j-1]);dp[i][j]=max(p1,p2);}}return dp[0][n-1];}
};

这个题需要一点小思考，想明白了就好写了。

首先是对于两人的得分，并不需要分别计算，只需要算出累加和后，计算一个人的得分，那么另一个人的就是累加和减去这个人的得分。

之后是求这一个人的最大得分。分析博弈的过程，可以发现，当前的人肯定是分成拿左侧和拿右侧两种情况，而选择的逻辑可以从让自己尽可能大转化成让对手尽可能小。所以对手肯定会尽可能让自己小，那就是两种情况再加上

前言

一、内容

二、题目

1.让字符串成为回文串的最少插入次数

2.预测赢家

相关文章：