【C++】20行带空间优化动态规划

class Solution {
public:
    int minEditCost(string &str1, string &str2, int &ic, int &dc, int &rc) {
        int num1 = str1.size(), num2 = str2.size();
        int dp[num2 + 1]; //记录每行遍历结果
        for(int j = 0; j <= num2; j++) dp[j] = j * ic; //长度0的str1到长度i的str2，全部插入代价最小
        for(int i = 1; i <= num1; i++ ) {
            int pre = dp[0]; //记录左上角的值
            dp[0] = i * dc; //长度i的str1到长度0的str2，全部删除代价最小
            for(int j = 1; j <= num2; j++) { //现在我们要求长度i的str1到长度j的str2的最小代价
                int insert = dp[j - 1] + ic; //长度i的str1到长度j-1的str2的最小代价上，加上插入str2[j-1]的代价
                int del = dp[j] + dc; //先有删除str1[i-1]的代价，再加上长度i-1的str1到长度j的str2的最小代价
                int modify = pre + (str1[i - 1] == str2[j - 1] ? 0 : rc); //长度i-1的str1到长度j-1的str2的最小代价上，加上不修改末位的代价0或修改末位的代价
                pre = dp[j]; //上面的值在下次循环时成为左上角的值
                dp[j] = min(insert, min(del, modify)); //获得当前最小代价
            }
        }
        return dp[num2]; //返回str1到str2的最小代价
    }
};