- 天河c线性dp时空优化
猴哥呆马的思路,有注释
- 2025-3-31 13:22:53 @
猴哥还是过于超标了
#include<iostream>
using namespace std;
string n;//字串
int mem[1145][1145];//mem[i][j]即为左i右j是最少需要插入的元素个数
int hgnb(int l,int r){
if(l>=r) return 0;//都不是个串了,0
if(mem[l][r]!=0) return mem[l][r];//有记录过,返回
if(n[l]==n[r]) return hgnb(l+1,r-1);//字符是一样的,无需操作,缩一层
else{
mem[l][r]=min(hgnb(l+1,r),hgnb(l,r-1))+1;//字符不一样,取左右插入中需要步数少的那一个,加上本次操作的1,返回
return mem[l][r];
}
}
int main(){
cin>>n;
cout<<hgnb(0,n.length()-1);
return 0;
}
1 comments
-
C24kongxiangtai LV 1 @ 2025-3-31 13:30:30
猴哥不削能玩?
- 1