正文索引 [隐藏]

动态规划是一个非常非常重要的算法。众所周知LeetCode周赛中十hard九dp，接触算法那么多年，动态规划始终没有做到完全的掌握，趁着这月LeetCode周赛的主题是dp，也争取完全掌握这门 算法。

内容会不定期更新，初步目标二十道，由易到难。

LeetCode-121:买卖股票的最佳时机

传送门

lc上的dp老题了，其实它只是借用了dp思想而已，和传统的dp有一点点差别。

首先考虑暴力做法。题意不难理解，找出数组中差值最大的两个数，输出他们的差值，要求较小数的下标要小于较大数。那么可以很简洁的写出一个直译：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int ans = 0;

        for(int i = 0; i < n; i++)
            for(int j = i; j < n; j++)
                ans = max(prices[j]-prices[i], ans);
        
        return ans;
    }
};

但是会在最后一个点超时。超时的原因是在枚举数字上浪费了太多时间，如果能在一个循环内完成对两个数的枚举自然就不会超时了。

用ans变量来记录答案，设置mini变量来维护数组最小值。状态转移方程即是：

ans = max(ans, prices[i] - mini);
mini = min(mini, prices[i]);

这样就可以计算出最大价值了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int ans = 0;
        int mini = INT_MAX;

        for(int i = 0; i < n; i++)
        {
            ans = max(ans, prices[i] - mini);
            mini = min(mini, prices[i]);
        }

        return ans;
    }
};

LeetCodeOffer-42:连续子数组的最大和

传送门

给出一个包含正负整数的数组，要求找到一组下标连续的子数组的最大和。

设dp[i]表示以nums[i]结尾的子数组的最大和。

考虑两种情况：

  1. dp[i-1]<0：即dp[i-1]对下一个状态做负贡献，此时dp[i-1]+nums[i]显然不如直接累加nums[i]；
  2. dp[i-1]>0：dp[i-1]可以做正贡献，此时正常累加。

根据上述思路可以得出状态转移方程：

dp[i] = max(dp[i-1] + nums[i], nums[i]);

对于所有的dp[i]，我们返回它们的最大值作为答案。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[100010];
        int ans = dp[0] = nums[0];

        for(int i = 1; i < n; i++)
        {
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            ans = max(dp[i], ans);
        }

        return ans;
    }
};

LeetCode-618:最长重复子数组

传送门

设dp[i][j]表示A数组后i个元素与B数组后j个元素中最长重复子数组的长度，初始状态为dp[alen][blen]=A[alen]==B[blen]?1:0，即从尾部往前计算。

状态转移方程为：

A[i]==B[j]：dp[i][j] = dp[i+1][j+1]+1;
A[i]!=B[j]：dp[i][j] = 0;

方程很好理解，如果当前元素相等，那么就在前一个状态的基础上加上一个单位的长度；如果不相等，当前情况自然就清零了，从下一个相等的字符开始重新计数。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int alen = A.size();
        int blen = B.size();
        int dp[1010][1010];
        int ans = 0;
        
        for (int i = alen - 1; i >= 0; i--) 
        {
            for (int j = blen - 1; j >= 0; j--) 
            {
                if(A[i] == B[j])
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                else 
                    dp[i][j] = 0;
                    
                ans = max(ans, dp[i][j]);
            }
        }

        return ans;
    }
};

LeetCode-64:最小路径和

传送门

经典的二维宫格最短路，从左上走到右下。设dp[i][j]表示从起点走到i,j的最短路，因为每一步只能走右或下，即当前状态只可能由左边或上边的状态得到。所以状态转移方程不难得出：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

初始条件下，预处理第一行与第一列的dp值用以计算。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        auto dp = vector< vector<int> >(n, vector<int>(m));

        dp[0][0] = grid[0][0];
        for(int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + grid[i][0];

        for(int i = 1; i < m; i++) dp[0][i] = dp[0][i-1] + grid[0][i];

        for(int i = 1; i < n; i++)
            for(int j = 1; j < m; j++)
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        
        return dp[n-1][m-1];
    }
};

LeetCode-62：不同路径

传送门

跟上一题有异曲同工的地方，依然是经典的走宫格。

设dp[i][j]表示从起点走到(i,j)的路径数。因为只能往下和往右，所以通往当前位置的路径数只与dp[i][j-1]和dp[i-1][j]有关，那么不难得到状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1];

初始状态下，第一列与第一行的dp值都为1，因为只有一种路径。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[110][110];

        for(int i = 0; i < m; i++)
            dp[i][0] = 1;
        for(int i = 0; i < n; i++)
            dp[0][i] = 1;

        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        
        return dp[m-1][n-1];   
    }
};

LeetCode-63：不同路径II

传送门

上一题的升级版，多了个障碍的设定。

显然，如果当前位置是障碍，那么肯定是走不通了，所以障碍位置的dp值一定是0。其他地方都和上一题一致。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        const int m = grid.size();
        const int n = grid[0].size();
        auto dp = vector< vector<int> >(m, vector<int>(n));
        //int dp[m][n];memset(dp, 0, sizeof(dp));

        if(m == 0) return 0;

        for(int i = 0; i < m && grid[i][0] == 0; i++) 
            dp[i][0] = 1;
        for(int i = 0; i < n && grid[0][i] == 0; i++) 
            dp[0][i] = 1;

        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                if(grid[i][j] == 0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
        
        return dp[m-1][n-1];
    }
};

LeetCode-343：整数拆分

传送门

划分型dp。显然，我们不难发现，每个整数拆分出的因子积取决于比他小的整数的因子积，所以可以用dp。假设dp[n]表示n的最大因子积。

对于每个整数i，拆分出因子j，此时获得的因子积为j*(i-j)，如果继续拆分，则因子积为j*dp[i-j]。所以，对于单个j，dp[i] = max(j*(i-j), dp[i-j])。因为j∈(0,i)，所以实际上dp[i]的值是对于取值范围中所有j求出的最大值。状态转移方程为：

dp[i] = max{max(j * dp[i-j], j * (i - j))};

那么不难得出答案：

class Solution {
public:
    int integerBreak(int n) {
        vector <int> dp(n+1);
        dp[0] = dp[1] = 0;

        for(int i = 2; i <= n; i++)
        {
            int cur = -INT_MAX;
            for(int j = 1; j < i; j++)
                cur = max(max(j * (i - j), j * dp[i-j]), cur);
            dp[i] = cur;
        }

        return dp[n];
    }
};

LeetCode-120：三角形最小路径

传送门

它曾经还是1994年IOI的竞赛题目，如今沦落为本蒟蒻的练手题…

又是最短路dp。这次的地图是三角形的，每次只能往下或往右下走，那么思路也是一样：

设dp[i][j]表示从起点到(i,j)的最短路径，与之前一样，可以根据题设得到状态转移方程：

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + grid[i][j];

初始条件下，三角形数组的高与斜边需要初始化。dp[i][0]的值就是第一列的前缀和，dp[i][i]的值也是dp[0][0]~dp[i-1][i-1]的前缀和，因为在高与斜边上的方格都有且仅有一条路径可以走。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& tri) {
        int ans = INT_MAX;
        int n = tri.size();
        vector< vector<int> >dp(n, vector<int>(n));
        
        dp[0][0] = tri[0][0];
        for(int i = 1; i < n; i++) 
        {
            dp[i][0] += dp[i-1][0] + tri[i][0];
            dp[i][i] += dp[i-1][i-1] + tri[i][i];
        }

        for(int i = 1; i < n; i++)
            for(int j = 1; j < i; j++)
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + tri[i][j];
            
        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};

LeetCode-647：回文子串

传送门

统计回文子串的题，其实回文串的dp都是一个套路，核心就是回文子串具有子结构性质。

与下一题相似，设dp[l][r]=1表示从第l个字符到第r个字符的子串是回文子串，那么有状态转移方程：

dp[l][r] = dp[l+1][r-1] && (s[l] == s[r]);

其中r=l+d，两层循环外层枚举子串长度d，内层枚举子串起始位置l。

最后用一个累加器统计答案，如果dp[l][r]=1就++。

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        bool dp[1010][1010];
        const int n = s.size();

        for(int d = 0; d < n; d++)
        {
            for(int l = 0; l < n; l++)
            {
                int r = l + d;
                if(r >= n) break;

                if(d == 0) dp[l][r] = 1;
                else
                    if(d == 1) dp[l][r] = (s[l] == s[r]);
                    else dp[l][r] = dp[l+1][r-1] && (s[l] == s[r]);
                
                if(dp[l][r]) ans++;
            }
        }
        
        return ans;
    }
};

LeetCode-5：最长回文子串

传送门

回文串具有很好的状态转移性质，因为一个回文串掐头去尾后它还是个回文串，这个结论是显然成立的。

根据上述思路，我们设dp[i][j]=1表示以第i个字符开头第j个字符结尾的子串是回文串。如果s[i]==s[j]并且dp[i+1][j-1]也等于1，那么显然当前子串也是回文串，至此我们可以得到状态转移方程：

dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];

具体实现上，外层循环枚举当前子串长度，内层循环枚举子串起始位置即可。

class Solution {
public:
    string longestPalindrome(string s) {
        string ans;
        const int n = s.size();
        vector< vector<bool> > dp(n, vector<bool>(n));

        for(int len = 0; len < n; len++)
        {
            for(int i = 0; i + len < n; i++)
            {
                int j = i + len;
                if(len == 0) dp[i][j] = 1;
                else
                    if(len == 1) dp[i][j] = s[i] == s[j];
                    else
                        dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
                
                if(dp[i][j] && len + 1 > ans.size())
                    ans = s.substr(i, len + 1);
            }
        }

        return ans;
    }
};