动态规划

最小编辑代价

http://www.nowcoder.com/questionTerminal/05fed41805ae4394ab6607d0d745c8e4

图片说明

 class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1,0x3f3f3f3f));
        for(int i=0;i<=str2.size();i++)
        {
            dp[0][i]=i*ic;//0个字符到i字符,需要插入
        }
        for(int i=0;i<=str1.size();i++)
        {
            dp[i][0]=i*dc;//i个字符到0字符,需要删除
        }
        for(int i=0;i<str1.size();i++)
        {
            for(int j=0;j<str2.size();j++)
            {
                if(str1[i]==str2[j])
                {
                    dp[i+1][j+1]=dp[i][j];
                }
                else
                {
                    int insertCost=dp[i+1][j]+ic;
                    int delCost=dp[i][j+1]+dc;
                    int repCost=dp[i][j]+rc;
                    dp[i+1][j+1]=min(insertCost,min(delCost,repCost));
                }
            }
        }
        return dp[str1.size()][str2.size()];
    }
};
全部评论

相关推荐

序&nbsp;朋友们,好久不见。&nbsp;笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬,一度丢失自己,觉得整个世界都是昏暗的。&nbsp;庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归,所以真的很开心还有机会能在再和大家见面。&nbsp;破碎秋招&nbsp;抑郁情绪的引爆点必然是秋招期间遭受的打击了,从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历,每天都在经历:简历挂、一面挂、二面挂、三面挂、HR面挂,每天睁开眼就被无所适从的挫败感包围。&nbsp;秋招的特点是即便流程走到最后一步也不一定会&nbsp;offer,因为还需要进入大池子进行横向对比,俗称泡池子,而这一泡我的大多数面试流程到后面就没了后文,这一度让我感觉非常绝望。我深知自己学历并...
SoNiC_X:我已经工作快2年了,当时高考没考好没去到想去的学校,觉得天要塌了;校招找不到工作,觉得天要塌了;现在工作觉得看不到未来,觉得天要塌了;最近最大的感悟就是:天会一直塌,但是生活也会一直继续下去,还是要调整好自己的心态,不要因为一时的困难把自己困住,要记住完蛋的日子永远在后头
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务