网易9.4 算法笔试

int get_min_count(string &s){     int len_s = s.length();     //cout << len_s;     s = " "+s;     int res  = INT_MAX;     vector<int> dp_r(len_s+1,0);     vector<int> dp_e(len_s+1,0);     vector<int> dp_d(len_s+1,0);     for(int i=1;i<=len_s;i++){         if(s[i]=='r&(31189)#39;){             dp_r[i] = min(dp_e[i-1],dp_d[i-1]);             dp_e[i] = min(dp_r[i-1]+1,dp_d[i-1]+1);             dp_d[i] = min(dp_r[i-1]+2,dp_e[i-1]+2);         }else if(s[i]=='e&(30300)#39;){             dp_r[i] = min(dp_e[i-1]+2,dp_d[i-1]+2);             dp_e[i] = min(dp_r[i-1],dp_d[i-1]);             dp_d[i] = min(dp_r[i-1]+1,dp_e[i-1]+1);         }else{              dp_r[i] = min(dp_e[i-1]+1,dp_d[i-1]+1);              dp_e[i] = min(dp_r[i-1]+2,dp_d[i-1]+2);              dp_d[i] = min(dp_e[i-1],dp_r[i-1]);         }     }     res = min(dp_r[len_s],dp_d[len_s]);     res = min(res,dp_e[len_s]);     return res; }

动态规划，参考股票那道dp题，维护三个dp数组

hi~同学，秋招遇“寒气”，牛客送温暖啦！23届秋招笔面经有奖征集中，参与就得牛客会员7天免费体验，最高赢300元京东卡！戳我去看>>>https://www.nowcoder.com/link/zhengjipinglun