动态规划专题

Posted on Edited on

动态规划解题模板和思路

动态规划套路

动态规划问题的一般形式是求最值，e.g. 最长递增子序列。

核心问题：穷举求最值.　不过，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

如何判断问题是否可以采用动态规划求解：

动态规划三要素:重叠子问题、最优子结构、状态转移方程, 如果能够列出来状态转移方程，算法的框架也就基本确定了，只需要考虑一些细节问题即可。

最优子结构

​ 可以从子问题的最优结果中推导出更大规模问题的最优结果

重叠的子问题

​ 可以采用递归调用树，如果递归调用树中存在多个相同的状态结点，则问题具有重叠的子问题

:star:思考状态转移方程的思维框架:

​ 明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

状态

​ 问题中可能会发生变化的变量，我们做选择的条件(划分了不同的子问题)

e.g. :　在0-1背包中，存在两个状态，「 背包的容量」和 「可选择的物品」

dp数组

​ dp概括了原问题和子问题的最优解的目标

​ e.g. 在0-1背包中，dp[i][j]表示对于前i个物品，当前背包的容量为j时.可以容纳的最大重量

选择

​ 导致状态转移的操作，在0-1背包中，表示第i个物品是否装入背包

base case

​ 初始化条件

其他问题
  • 如何遍历dp表呢？

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置。

相关文章

动态规划 v.s. 回溯

  • 如何理解回溯和动态规划之间的关系？

​ 目前我认为回溯是自顶向下求解，可以利用备忘录优化( C++的备忘录，可以采用 vector<int>mem　存储某个状态下dp的内容,也可以用 unordered_map<string, int> string是状态下标转换的字符)

​ 动态规划是自低向上求解，是利用循环遍历代替暴力递归的一种思路(回溯大多是暴力递归).

可以参考下面的文章中的例子仔细体会

相关例题

背包问题

常见的0-1背包的问题描述：给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

字符串类

解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

10.正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

1
2
>输入：s = "aa" p = "a*"
>输出：true
动态规划思路

按照上面介绍的过程分析一下吧！

​ 明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

状态：在s,p匹配过程中，状态有两个：匹配到s串的位置i, 匹配到p串的位置j

定义dp含义：题目要求是判断两个串是否匹配成功,　dp[i][j]表示s[:i] 和 p[:j]两个子串是否匹配,为true　表示匹配成功，否则失败

最终目标是求得dp[s.size()][p.size()]的值

选择：这里的选择感觉指的是　如果当前p串要匹配的字符是*，s串是选择匹配０个／1个／多个

base case以及一些细节信息：如果出现空串如何匹配

为了方便计算，我们定义dp[i+1][j+1]表示s[:i] 和 p[:j]的匹配结果，并且dp[0][0]=true,

同时考虑到，如果出现s为空串，p为”#*"类型，e.g. s=””,p=”a*”,

1
2
s=' '+s;
p=' '+p;

如果不设置这个，不会进入状态转移判断方程，直接退出循环，误判为　匹配失败。

dp转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isMatch(string s, string p) {
    s=' '+s;
    p=' '+p;
    int n=s.size();
    int m =p.size();
    vector<vector<bool>> dp (n+1,vector<bool>(m+1,false));
    dp[0][0]=true;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i]==p[j] || p[j]=='.'){
                dp[i+1][j+1]=dp[i][j];
            }
            else if(p[j]=='*'){
                int flag = s[i]==p[j-1] || p[j-1]=='.';
                dp[i+1][j+1] = (flag && (dp[i][j+1] || dp[i+1][j]) )||(dp[i+1][j-1]);
            }
        }
    }
    return dp[n][m];
}
待备忘录的暴力搜索

(不增加备忘录，会出现超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
unordered_map<string,int> dp;
bool caldp(int i,int j,string s,string p){
    if(j==p.size())
        return i == s.size();

    if(dp[i][j]!=-1){
        return dp[i][j];
    }

    else{
        bool flag = i<s.size() && (s[i]==p[j] || p[j]=='.');
        if(j<p.size()-1 && p[j+1]=='*'){
            dp[i][j]= caldp(i,j+2,s,p) || (flag && caldp(i+1,j,s,p));
            return dp[i][j];
        }else{
            dp[i][j]=flag && caldp(i+1,j+1,s,p);
            return dp[i][j];
        }
    }
}
bool isMatch(string s, string p) {
    int slen=s.size();
    int plen = p.size();
    for(int i=0;i<slen+1;i++){
        dp.push_back(vector<int>(plen,-1));
    }
    return caldp(0,0,s,p);
}

其他

494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3