定义及分类

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

Code实例

01Bag

题目

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

主要思路

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

物品数\质量012345678910
000000000000
100666666666
200669999999
300669999111114
4006699910111314
50066991212151515

核心代码

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

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继续加，继续往后会变小
每一步取最大

核心代码

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的结果

核心代码

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的结果
}