题解 | #编辑距离(二)#

#include <vector>
class Solution {
  public:
    void dp_show( vector<vector<int>> dp)
    {
         for (int i = 0; i < dp.size(); ++i) {
            for (int j = 0; j < dp[0].size(); ++j) {
                cout<<dp[i][j]<<"  ";
            }
            cout<<endl;
        }
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 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) {
        //dp[i][j]表示s1[i]变为s2[j]需要的代价值
        vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1, 0));

        //将str1变为空需要删除元素
        for (int i = 0; i < dp.size(); ++i) {
            dp[i][0] = i * dc;
        }

        //str1为空变为str2需要添加元素
        for (int i = 0; i < dp[0].size(); ++i) {
            dp[0][i] = i * ic;
        }

        //二维动态规划
        for (int i = 1; i < dp.size(); ++i) {
            for (int j = 1; j < dp[0].size(); ++j) {
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + ic;
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + dc);
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + rc);
                }
            }
        }
        dp_show(dp);
        return dp[dp.size()-1][dp[0].size()-1];
    }
};