动态规划

动态规划问题

  • 动态规划问题的核心思想就是穷举求最值，一定存在具备最有结构和存在重叠子问题；列出正确的状态转移方程才能正确地穷举。

    如何列出正确的状态转移方程

  1. 确定base case

  2. 确定状态，也就是原问题和子问题中会变化的变量

  3. 确定选择，也就是导致状态产生变化的行为

  4. 明确dp函数/数组的定义

    礼物的最大价值

    题目如下：

  • 这题考虑用dfs，因为很多重复的问题
  • 或者是用相同规模的数组来处理这个问题
  • 或者将二维数组压缩成一维数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        int maxValue(vector<vector<int>>& grid) {
            int n = grid[0].size(), m = grid.size();
            vector<int> dp(n+1,0);
            for(int i = 1; i <= m ; ++i){
                for(int j = 1; j <= n; ++j){
                    dp[j] = max(dp[j-1],dp[j])+grid[i-1][j-1];
                }
            }
            return dp[n];
        }
    };
    参考文献

连续子数组的最大和

题目如下：

  • 这道题目比较简单，就是如何判定从数组内i到j累加结束？
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        for(int i = 1;i < nums.size(); ++i){
            nums[i] += max(nums[i-1],0);
            ans = max(ans,nums[i]);
        }
        return ans;
    }
};


参考文献

股票的最大利润

题目如下：

  • 主要是去寻找最低价格和最高的利润

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.size() == 0)return 0;
            int begin_num = prices[0];  //买入价格
            int end_num = 0;    //利润
            for(int i = 1;i < prices.size(); ++i){
                begin_num = min(prices[i], begin_num); //这一步主要是找最低的购买价格
                end_num = max(end_num, prices[i] - begin_num);
            }
            return end_num;
        }
    };

    参考文献

正则表达式匹配

题目如下：

如何去处理那两个特殊的符号，然后再应用到程序中
一个就是dp数组来处理，分清楚步骤和判断条件


给出代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size() + 1, n = p.size() + 1;
        vector<vector<bool>> dp(m, vector<bool>(n, false));
        dp[0][0] = true;
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = p[j - 1] == '*' ?
                    dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):
                    dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

参考文献