定义及分类

多阶段决策过程的最优化问题。
动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。

Code实例

01Bag

题目

01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为$W_1$,$W_2$至$W_n$,与之相对应的价值为$P_1$,$P_2$至$P_n$。
在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。
求解将哪些物品装入背包可使价值总和最大。

主要思路

每一个物品有2种状态:不装(0)和装(1),将其分解后的最终问题是能不能放进这个物品?
我们可以构建如下表格
每一栏表示在当前最大重量和物品数的时候的最大价值
最大重量:10
重量:{2,2,6,5,4}
价值:{6,3,5,4,6}
以如上数据为例,根据状态转移方程,可构建如下表格。

物品数\质量 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 6 6 6 6 6 6 6 6 6
2 0 0 6 6 9 9 9 9 9 9 9
3 0 0 6 6 9 9 9 9 11 11 14
4 0 0 6 6 9 9 9 10 11 13 14
5 0 0 6 6 9 9 12 12 15 15 15

核心代码

cont:物品数量 maxw:最大重量 bag:表示背包的二维数组

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=cont;i++){
for (int j = 1;j<=maxw;j++){
if(j>=weights[i]){
//如果当前重量>=最大重量
bag[i][j] = max(bag[i - 1][j], bag[i - 1][j - weights[i]] + values[i]);
}else{
bag[i][j] = bag[i - 1][j];
}
}
}

cout<<bag[cont][maxw]<<endl;

最大子序和

题目

LeetCode
给定一个整数数组,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

主要思路

从前往后依次加
遇到负数归0继续加,继续往后会变小
每一步取最大

核心代码

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(vector<int>& nums) {
int maxn = INT_MIN;
int result = 0;
for(int i = 0; i < nums.size(); i++)
{
if(result < 0) result=0;
result+=nums[i];
maxn = max(maxn,result);
}
return maxn;
}

正则表达式匹配

题目

LeetCode
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘‘ 的正则表达式匹配。
‘ 匹配零个或多个前面的元素
‘.’ 匹配任意单个字符。
匹配应该覆盖整个字符串 (s) ,而不是部分字符串。

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。

主要思路

  • 若p为空,且s也为空,返回true,反之返回false

  • 若p的长度为1,且s长度也为1,且相同或是p为’.’则返回true,反之返回false

  • 若p的第二个字符不为*,且此时s为空则返回false,否则判断首字符是否匹配,且从各自的第二个字符开始调用递归函数匹配

  • 若p的第二个字符为*,s不为空且字符匹配,调用递归函数匹配s和去掉前两个字符的p,若匹配返回true,否则s去掉首字母

  • 返回调用递归函数匹配s和去掉前两个字符的p的结果

核心代码

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
bool isMatch(string s, string p)
{
if (p.empty())
return s.empty();
//若p为空,且s也为空,返回true,反之返回false
if (p.size() == 1)
return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
//若p的长度为1,且s长度也为1,且相同或是p为'.'则返回true,反之返回false
if (p[1] != '*')
{
if (s.empty())
return false;
return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
//若p的第二个字符不为*,且此时s为空则返回false,否则判断首字符是否匹配,且从各自的第二个字符开始调用递归函数匹配
while (!s.empty() && (s[0] == p[0] || p[0] == '.'))
{
if (isMatch(s, p.substr(2)))
return true;
s = s.substr(1);
}
//若p的第二个字符为*,s不为空且字符匹配,调用递归函数匹配s和去掉前两个字符的p,若匹配返回true,否则s去掉首字母
return isMatch(s, p.substr(2));
//返回调用递归函数匹配s和去掉前两个字符的p的结果
}