编辑距离(二)

/**
 * 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(char* s, char* t, int ic, int dc, int rc ) {
    // write code here
    int m = strlen(s);
    int n = strlen(t);
    // if (m >= n + 2)
    //     return false;
    int** mined = (int**)malloc(sizeof(int*) * (m + 1));
    for (int i = 0; i <= m; i++) {
        mined[i] = (int*)calloc(n + 1, sizeof(int));
    }
    for (int ii = 1; ii <= m; ii++) {
        mined[ii][0] = ii*dc;
    }
    for (int iii = 1; iii <= n; iii++) {
        mined[0][iii] = iii*ic;
    }
    for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= n; k++) {
            if (s[j - 1] == t[k - 1]) {
                mined[j][k] = mined[j - 1][k - 1];
            } else {
                if ((mined[j - 1][k - 1] + rc) < (mined[j][k - 1] + ic)) {
                    if ((mined[j - 1][k - 1] + rc) < (mined[j - 1][k] + dc)) {
                        mined[j][k] = (mined[j - 1][k - 1] + rc);
                    } else {
                        mined[j][k] = (mined[j - 1][k] + dc);
                    }
                } else {
                    if ((mined[j][k - 1] + ic) < (mined[j - 1][k] + dc)) {
                        mined[j][k] = (mined[j ][k - 1] + ic);
                    } else {
                        mined[j][k] = (mined[j - 1][k] + dc);
                    }

                }
                //mined[j][k]=((mined[j-1][k-1]+1)>(mined[j][k-1]+1):)
            }
        }
    }
    // if (mined[m][n] == 1)
    //     return true;
    return mined[m][n];
}