动态规划——从0-1背包问题到leetcode正则匹配

下列是我们熟悉的背包问题的描述：

有n个物体，每个物体有一定的体积( v i v_i vi​)，和一定的价值( p i p_i pi​)。我们想挑选一些物品放入 容量为V的背包里，希望放进去的物体价值最大。

显然其中标红的部分是核心，即在一个限制条件下，将价值最大化。就和机器学习的损失函数一样，将函数最优化。

对于损失函数，我们可以基于问题是分类还是回归，来自己选定；对于我们的背包问题的价值最大化，没有一个固定式进行优化，所以很重要的一件事是我们需要找到一个结构和它的一个模式亦或是数学表达式（状态转移方程）

一般我们可以通过枚举观察来找出。
比如有两个数组：

进行尝试，我们知道我们需要进行不断尝试（至少两轮循环）

从上图的观察，我们选用一个二维数组作为存储结构，第一维索引我们存储的信息是放入物体的个数，第二维索引我们存放物体的体积(整数连续)，数组内存放的信息是，在存放i个物体下，体积达到j的时候最大的价值。
基于这样的结构，我们的状态转移方程存在两个种迭代方式：
加入一个物体，逐步变量连续的体积

1. 体积小于加入物体的体积：当前位置的价值(f[i][j])等于未加入该物体的时候的价值(f[i-1][j]) (即f[i][j] = f[i-1][j])
2. 体积大于加入物体的体积：当前位置的价值(f[i][j]) 有两部分比较后更新 (即f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + p[i])
   a. 未加入该物体的时候的价值(f[i-1][j]
   b. 加入该物体的时候的价值(f[i-1][j - v[i]] + p[i]) 将体积返回到放入物体之前j-v[i] 然后加上该物体的价格 p[i]

基于上述的分析，我们很容易写出解决方案(时间复杂度T(nV)，空间复杂度O(nV))

#include 
using namespace std;

int main(){
    int v[4]={10, 8, 30, 16};
    int p[4]={99, 18, 20, 56};
    int V=40;
    int f[5][41];
    for(int i=0; i<5; i++) for(int j=0;j<41;j++) f[i][j]=0;
    for(int i=1; i<5; i++){
        for(int j=1; j<=V; j++){
            cout << "BF: f[" << i << "][" << j << "]=" << f[i][j];
            if(i==0){
                f[0][j]=0;
            }else if(j < v[i-1]){
                f[i][j]=f[i-1][j];
            }else{
                f[i][j]=max(f[i-1][j], f[i-1][j-v[i-1]]+p[i-1]);
            }

            cout << " | AFT: f[" << i << "][" << j << "]=" << f[i][j] << endl;;
        }
    }
    cout<< f[4][40] << endl;
    return 0;
}

def pkg_solve(V: int, v_list: list, p_list: list):
    obj_cnt = len(v_list)
    p_arr=[
        [0] * (V+1) for _ in range(obj_cnt+1)
    ]
    print(obj_cnt, len(p_arr), len(p_arr[0]))
    for i in range(1, obj_cnt+1):
        print(i)
        for j in range(1, V+1):
            if(j < v_list[i-1]): p_arr[i][j] = p_arr[i-1][j]; continue;
            print(f'BF: p_arr[{i}][{j}]={p_arr[i][j]}', end=" ")
            p_arr[i][j]=max(
                p_arr[i-1][j], 
                p_arr[i-1][j - v_list[i-1]] + p_list[i-1]
            );
            print(f'| AFT: p_arr[{i}][{j}]={p_arr[i][j]}')
    return p_arr[obj_cnt][V]


v_list=[10, 8, 30, 16]
p_list=[99, 18, 20, 56]
V=40;

pkg_solve(V, v_list, p_list)

从结果上我们可以看出，序列仅仅在后面部分进行了更新， 所以我们可以将空间复杂度降低为O(V)

int main(){
    int v[4]={10, 8, 30, 16};
    int p[4]={99, 18, 20, 56};
    int V=40;
    int f[41];
    for(int i=0; i<41; i++)  f[i]=0;
    for(int i=0; i<5; i++){
        for(int j=V; j>=v[i-1]; j--){
            f[j]=max(f[j], f[j-v[i-1]]+p[i-1]);
        }
    }
    cout<< f[40] << endl;
    return 0;
}

def update_pkg_solve(V: int, v_list: list, p_list: list):
    obj_cnt = len(v_list)
    p_arr = [0] * (V+1)
    for i in range(1, obj_cnt+1):
        for j in range(V, v_list[i-1]+1, -1):
            p_arr[j]=max(
                p_arr[j], 
                p_arr[j - v_list[i-1]] + p_list[i-1]
            );    
    print(p_arr)
    return p_arr[V]


v_list=[10, 8, 30, 16]
p_list=[99, 18, 20, 56]
V=40;

update_pkg_solve(V, v_list, p_list)

之前我们的优化都是基于整数情况，当是浮点数据的时候，数组就不是那么好做了。
我们可以直接优化为一个分段更新的分段函数， 一个记录分段的时候的体积，一个记录分段时候的价值。
这样就按上面的思路就可以写出我们最终的优化解。

#include 
using namespace std;

int main(){
    float v[4]={10.24, 8.1, 30.6, 16.8};
    float p[4]={99, 18, 20, 56};
    float V=40.8;

    int v_len = sizeof(v)/sizeof(float);
    int V_ceil = V / 1;
    V_ceil+=1;
    float break_point[42] = {0};
    float weight_point[42] = {0};
    int break_cnt = 1;
    int v_tmp=0;
    for(int i=1; i < v_len+1; i++){
        cout << "====================================" << endl;
        cout << i << " ";
        v_tmp = v[i-1] / 1;
        v_tmp++;
        cout << v[i-1] << " " << v_tmp << endl;
        for(int j=V_ceil; j >= v_tmp; j--){
            if(weight_point[break_cnt-1] + v[i-1] > V) break;
            if(
                (break_point[break_cnt-1] + p[i-1] > break_point[break_cnt-1]) &&
                (weight_point[break_cnt-1] + v[i-1] > weight_point[break_cnt-1])
            ){
                break_point[break_cnt] = break_point[break_cnt-1] + p[i-1];
                weight_point[break_cnt] = weight_point[break_cnt-1] + v[i-1];
                break_cnt+=1;
                break;
            }
        }
    }

    cout << break_cnt << endl;
    for (int i=0; i< break_cnt; i++) cout << break_point[i] << " ";
    cout << endl;
    for (int i=0; i< break_cnt; i++) cout << weight_point[i] << " ";
    cout << endl;

    cout << "res=" << break_point[break_cnt-1];
    return 0;
}

def float_pkg_solve(V: float, v_list: list, p_list: list):
    obj_cnt = len(v_list)
    break_point = [0]
    weight_point = [0]
    break_cnt = 1
    for i in range(1, obj_cnt+1):
        for j in range(int(V) + 1, int(v_list[i-1])+1, -1):
            if weight_point[break_cnt-1] + v_list[i-1] > V:
                break
            if (break_point[break_cnt-1] + p_list[i-1] > break_point[break_cnt-1])
            and (weight_point[break_cnt-1] + v_list[i-1] > weight_point[break_cnt-1]):
                break_point.append(
                    break_point[break_cnt-1] + p_list[i-1]
                )
                weight_point.append(
                    weight_point[break_cnt-1] + v_list[i-1]
                )
                break_cnt += 1
                break

    print(break_point)
    print(weight_point)
    return break_point[-1]



v_list = [10.24, 8.1, 30.6, 16.8]
# v_list=[10, 8, 30, 16]
p_list=[99, 18, 20, 56]
# p_list=[99, 18, 20, 506]
V = 40.8


float_pkg_solve(V, v_list, p_list)

https://leetcode-cn.com/problems/regular-expression-matching/
其实就只有用判断两个情况，后面带*不带*。对于带*分成两种， 一种是.*一种是x*

#include 
#include 
using namespace std;


class Solution {
public:
    bool isMatch(string s, string p) {
        return __isMatch(s.c_str(), p.c_str());
    }

private:
    bool __isMatch(const char* s, const char* p) {
        if(*p == 0) return *s == 0;
        
        bool first_match = *s && (*s == *p || *p == '.');
        
        // .* x*
        if(*(p+1) == '*'){
            return isMatch(s, p+2) || (first_match && isMatch(++s, p));
        }
        else{
            return first_match && isMatch(++s, ++p);
        }
    }
};


int main(){
    string str_ = "ab";
    string pattern = ".*";
    Solution sl=Solution();
    bool out;
    
    cout << "=====================" << endl;
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;

    cout << "=====================" << endl;
    str_ = "aaa";  pattern = "a*";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;

    cout << "=====================" << endl;
    str_ = "aaa";  pattern = "a*c*";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;


    cout << "=====================" << endl;
    str_ = "ab";  pattern = ".*c";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;

    cout << "=====================" << endl;
    str_ = "aab";  pattern = "c*a*b";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;

    cout << "=====================" << endl;
    str_ = "mississippi";  pattern = "mis*is*p*.";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;


    cout << "=====================" << endl;
    str_ = "aaa";  pattern = "aaaa";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;

    cout << "=====================" << endl;
    str_ = "aaa";  pattern = "ab*a*c*a";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;


    cout << "=====================" << endl;
    str_ = "ab";  pattern = ".*c*";
    out = sl.isMatch(str_, pattern);
    cout << "s=" << str_ << " pattern=" << pattern << " | result=" << out << endl;
    return 0;

}

def isMatch(s, p):
    if(p == ''):
        return s == '';

    fst = False
    if s != '':
        fst = s[0] and ((s[0] == p[0]) or (p[0] == '.'))

    print(f's={s} p={p} fst={fst}')
    if(len(p) >= 2 and p[1] == '*'):
        if len(s):
            return isMatch(s, p[2:]) or (fst and isMatch(s[1:], p))
        else:
            return isMatch(s, p[2:]) or (fst and isMatch("", p))
    return fst and isMatch(s[1:], p[1:])


if __name__ == '__main__':
    str_ = "ab";
    pattern = ".*c*";
    result = isMatch(str_, pattern)
    print(f"result={result}")

    str_ = "ab";
    pattern = ".*c";
    result = isMatch(str_, pattern)
    print(f"result={result}")