动态规划的几种实现方式

动态规划又几种不同的实现方式，以leetcode第1143题为例：

很明显这是一道动态规划的题，而动态规划有多种不同的实现方式，比如最常见的两种方式是迭代递推法和记忆化搜索法，这两种方法的主要区别在于，迭代递推法是自底向上递推，而记忆化搜索是自顶向下搜索，在搜索过程中保存计算结果，避免重复计算。

递归搜索 + 保存计算结果 = 记忆化搜索

class Solution {
private:
    vector<vector<int>> memo;
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        int len1 = text1.size(), len2 = text2.size();
        memo = vector<vector<int>>(len1, vector<int>(len2, -1));
        return dp(text1, len1 - 1, text2, len2 - 1);
    }

    int dp(const string &text1, int end1, const string &text2, int end2)
    {
        if(end1 == -1 || end2 == -1)
            return 0;
        if(memo[end1][end2] != -1)
            return memo[end1][end2];

        if(text1[end1] == text2[end2])
            memo[end1][end2] = dp(text1, end1 - 1, text2, end2 - 1) + 1;
        else
            memo[end1][end2] = max(dp(text1, end1 - 1, text2, end2), dp(text1, end1, text2, end2 - 1));
        return memo[end1][end2];
    }
};

迭代递推

class Solution {
private:
    vector<vector<int>> memo;
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        int len1 = text1.size(), len2 = text2.size();
        memo = vector<vector<int>>(len1 + 1, vector<int>(len2 + 1, 0));
        memo[0][0] = memo[1][0] = memo[0][1] = 0;
        for(int i = 0; i < len1; ++i)
        {
            for(int j = 0; j < len2; ++j)
            {
                if(text1[i] == text2[j])
                    memo[i + 1][j + 1] = memo[i][j] + 1;
                else    
                    memo[i + 1][j + 1] = max(memo[i][j + 1], memo[i + 1][j]);
            }
        }
        return memo[len1][len2];
    }

};

空间优化（一个数组）

class Solution {
private:
    vector<int> memo;
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        int len1 = text1.size(), len2 = text2.size();
        memo = vector<int>(len2 + 1, 0);
        int pre = 0;
        for(int i = 0; i < len1; ++i)
        {   
            pre = 0;        // 每次++i之后j又从0开始，pre = memo[j] = 二维memo[i][0] = 0
            for(int j = 0; j < len2; ++j)
            {   
                int tmp = memo[j + 1];      // temp == 二维memo[i][j + 1]
                if(text1[i] == text2[j])
                    memo[j + 1] = pre + 1;   // memo[j + 1] == 二维memo[i + 1][j + 1]
                else    
                    memo[j + 1] = max(tmp, memo[j]);     // memo[j + 1] == 二维memo[i + 1][j + 1]
                pre = tmp;
            }
        }
        return memo[len2];
    }

};