动态规划

2019/10/11 Algorithm

动态规划的问题一般形式是求最值,主要的技术细节是寻找重叠子问题、最优子结构以及状态转移方程。一般解决问题的思路是首先确定该问题存在重叠子问题,然后定义其状态转移方程,紧接着确定dp数组的边界,最后考虑是否存在dp数组的优化。下面讨论一些经典的DP问题以及解决方法。

子序列问题

最长公共子序列

给定两个字符串A、B,求解这两个字符串的最长公共子序列。定义dp[i][j]为字符串A的子串[0…i]与字符串B的子串[0…j]的最长公共子序列。有状态转移方程:

if A[i] == B[j]
    dp[i][j] = dp[i-1][j-1] + 1
else
    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
// LeetCode 1143.Longest Common Subsequence
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; i++){
            dp[i][0] = 0;
        }
        for(int i=0; i<=n; i++){
            dp[0][i] = 0;
        }
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(text1[i-1] == text2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

最长回文子序列

给定一个字符串A,求解这个字符串的最长回文子序列。定义dp[i][j]为字符串A的子串[i…j]的最长回文子序列。有状态转移方程:

if A[i] == B[j]
    dp[i][j] = dp[i+1][j-1] + 2
else
    dp[i][j] = max(dp[i][j-1], dp[i+1][j])
// LeetCode 516.Longest Palindromic Subsequence
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();
        vector<vector<int> > dp(len, vector<int>(len, 0));
        for(int i=0; i<len; i++)
            dp[i][i] = 1;
        for(int i=len-1; i>=0; i--){
            for(int j=i+1; j<len; j++){
                if(s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }
};

最长递增子序列

给定一组整数数组nums,求解出其最长递增子序列。定义dp[i]为子数组nums[0…i]的最长递增子序列。有状态转移方程:

for(int j=0; j<i; j++)
    if(nums[i] > nums[j])
        dp[i] = max(dp[i], dp[j] + 1);
// LeetCode 300.Longest Increasing Subsequence
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        vector<int> dp(nums.size(), 1);
        for(int i=1; i<dp.size(); i++){
            for(int j=i-1; j>=0; j--){
                if(nums[i]>nums[j]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int kls : dp){
            // cout << kls << " ";
            res = max(res, kls);
        }
        return res;
    }
};

编辑距离问题

给定两个字符串A、B以及三个操作:插入、删除、替换一个字符,求出将字符串A转为成字符串B的最少操作次数。该问题的状态转移方程与最长公共子序列的方程类似。

// LeetCode 72.Edit Distance
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > dp(m+1, vector<int>(n+1));
        for(int i=0; i<=m; i++){
            dp[i][0] = i;
        }
        for(int i=0; i<=n; i++){
            dp[0][i] = i;
        }
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

DP的优化,使用一维DP数组:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int a = word1.size();
        int b = word2.size();
        vector<int> dp(a+1, 0);
        for(int i=0; i<=a; i++)
            dp[i] = i;
        for(int i=1; i<=b; i++){
            int prev = dp[0];
            dp[0] = i;
            for(int j=1; j<=a; j++){
                int temp = dp[j];
                if(word1[j-1] == word2[i-1])
                    dp[j] = prev;
                else
                    dp[j] = 1 + min(prev, min(dp[j], dp[j-1]));
                prev = temp;
            }
        }
        return dp[a];
    }
};

博弈问题

给定一个整数数组,分先手和后手每次从左、右两边取一个数,数和最大者获胜。当先后手的决策都是最优的情况下,求先后手谁能获胜。这个依旧是动态规划问题,稍微变化的是这里的DP数组储存的是一个数对,详尽的解析见这个链接

Tips: 创建一个数对的API是make_pair。

Tips: 二维数组上三角遍历下标的循环代码:

for(int t=1; t<len; t++){
    for(int i=0; i<len-t; i++){
        int j = t+i;
    }
}
// LeetCode 877.Stone Game
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int len = piles.size();
        vector<vector<pair<int, int> > > dp(len, vector<pair<int, int> >(len));
        for(int i=0; i<len; i++){
            dp[i][i] = make_pair(piles[i], 0);
        }
        for(int l=1;l<len;l++){
            for(int i=0;i<len-l;i++){
                int j=l+i;
                int L = piles[i] + dp[i+1][j].second;
                int R = piles[j] + dp[i][j-1].second;
                if(L > R){
                    dp[i][j] = make_pair(L, dp[i+1][j].first);
                } else {
                    dp[i][j] = make_pair(R, dp[i][j-1].first);
                }
            }
        }
        return dp[0][len-1].first - dp[0][len-1].second;
    }
};

##

Search

    Table of Contents