|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
对这种第n个决策只和第n-1个决策相关的情况,很容易想到dp,这里令f[0]【i】表示让s[0~i]以0为结尾所需进行的删除操作,用f[1]【i】表示以1为结尾所需进行的删除操作,对s【i】分类讨论我们容易得出:
(1)s【i】=0,则f[0]【i】=min(f[0][i-1]+1, f[1][i-1]),且f[1]【i】=f[1][i-1]+1
(2)s【i】=1,则f[1]【i】=min(f[1][i-1]+1, f[0][i-1]),且f[0]【i】=f[0][i-1]+1
需要注意的是转移方程中的边界条件,如果s[0~i]都是0的话,则f[1]【i】就是Inf,如果s[0~i]都是1的话,则f[0][1]就是Inf,因为这两种情况下无论如何都不能让删除后的string以0或1结尾
- #include <vector>
- using std::vector;
- class Solution {
- /*
- f[0]【i】 represents the minimum deletes we need to make s[0~i] meet the requirements and ends with '0'
- f[1]【i】 represents the minimum deletes we need to make s[0~i] meet the requirements and ends with '1'
- */
- vector<int> f[2];
- public:
- int leastDeletion(string &s) {
- int n = s.size();
- if(n < 2) return 0;
-
- //allocate memory
- f[0].resize(n);
- f[1].resize(n);
- //initialize
- if(s[0] == '0'){
- f[0][0] = 0;
- f[1][0] = n;
- }
- else{
- f[0][0] = n;
- f[1][0] = 0;
- }
- //dp
- for(int i = 1; i < n; ++i){
- if(s【i】 == '0'){
- f[0]【i】 = min(i, min(f[0][i-1] + 1, f[1][i-1]));
- f[1]【i】 = min(n, f[1][i-1] + 1);
- }
- else{
- f[0]【i】 = min(n, f[0][i-1] + 1);
- f[1]【i】 = min(i, min(f[0][i-1], f[1][i-1] + 1));
- }
- }
- return min(f[0][n-1], f[1][n-1]);
- }
- };
复制代码
|
|