题目:
现有一个 n 位数，你需要删除其中的 k 位，请问如何删除才能使得剩下的数最大？
比如当数为 2319274， k=1 时，删去 2 变成 319274 后是可能的最大值。
思路：
1、贪心算法
每次从高位向低位数，删除高位数字比低位数字小的那位数字。如2319274
第一次2<3，删除2，得到319274
第二次3>1,略过，1<9,删除1，得到39274
第三次3<9，删除3，得到9274
。。。。。。
// greedy method
string deleteKBits_1(string str,int k){
int tlen=str.length();
bool flag=true;
int len;
while(k && flag){
len=str.length();
for(int i=0;i<len-1;i++){
if(str[i]<str[i+1]){
str.erase(i,1);
flag=true;
break;
}
}
k--;
}
return str.substr(0,tlen-k);
}
2、动态规划
分析：
假设str为长度为n的数字字符串,S[i][j]表示删除str[0...i-1]中j个数字后的最大字符数字。
如果删除第i个数，则S[i][j]等于删除前i-1个字符中的j-1位的最优解，即S[i][j]=S[i-1][j-1];
如果不删除第i个数，则S[i][j]等于删除前i-1个字符中j位的最优解+str[i]，即S[i][j]=S[i-1][j]+str[i-1];
即S[i][j]=max(S[i-1][j-1],S[i-1][j]+str[i-1])
初始状态为当j=0时，不删除任何位的数字，即S[i][j]=str[0...i-1]；
状态转移方程如下：
S[i][j]=
strsub(0,i); (if j==0)
max(S[i-1][j-1],S[i-1][j]+str[i-1]); (if 0<j<i;0<j<=k)
时间复杂度：O(n*k)
空间复杂度：O(n*k)
优化：
从上述的转移方程S[i][j]=max(S[i-1][j-1],S[i-1][j]+str[i-1])，可以看出在每一次i循环中，只与i-1相关，因此不需要用单独使用一个维度的数组来存储，只需要每次通过一个变量last保存上一次的结果。因此转移方程可以简化为S[j]=max(last,S[j]+str[i-1]）
时间复杂度：O(n*k)
空间复杂度：O(k)
// dynamic programming
// time complexity: O(n*k)
// space complexity: O(n*k)
string deleteKBits_2(string str,int k){
int tlen=str.length();
vector<vector<string> > nums(tlen+1,vector<string>(k+1));
string s1,s2;
for(int i=1;i<=tlen;i++){
for(int j=0;j<i && j<=k;j++){
if(j==0){
nums[i][j]=str.substr(0,i);
}
else{
s1=nums[i-1][j-1];
s2=nums[i-1][j]+str[i-1];
if(s1.compare(s2)<=0)
nums[i][j]=s2;
else
nums[i][j]=s1;
}
}
}
return nums[tlen][k];
} // dynamic programming
// time complexity: O(n*k)
// space complexity: O(k)
string deleteKBits_3(string str,int k){
int tlen=str.length();
vector<string> nums(k+1);
string s1,s2,last;
for(int i=1;i<=tlen;i++){
for(int j=0;j<i && j<=k;j++){
if(j==0){
last=nums[j];
nums[j]=str.substr(0,i);
}
else{
// s1=last
s1=nums[j-1];
s2=nums[j]+str[i-1];
if(s1.compare(s2)<=0){
last=nums[j];
nums[j]=s2;
}
else{
last=nums[j];
nums[j]=s1;
}
}
}
}
return nums[k];
} // dynamic programming
// time complexity: O(n*k)
// space complexity: O(k)
string deleteKBits_4(string str,int k){
int tlen=str.length();
vector<string> nums(k+1);
string tmp,s2,last;
for(int i=1;i<=tlen;i++){
for(int j=0;j<i && j<=k;j++){
if(j==0){
last=nums[j];
nums[j]=str.substr(0,i);
}
else{
// s1=last
// s1=nums[j-1];
s2=nums[j]+str[i-1];
if(last.compare(s2)<=0){
last=nums[j];
nums[j]=s2;
}
else{
tmp=nums[j];
nums[j]=last;
last=tmp;
}
}
}
}
return nums[k];
}
运行结果：
int main()
{
string str="2319274";
int k=3;
cout <<deleteKBits_1(str,k)<< endl;
cout <<deleteKBits_2(str,k)<< endl;
cout <<deleteKBits_3(str,k)<< endl;
cout <<deleteKBits_4(str,k)<< endl;
return 0;
}