第五章 动态规划（一）

1. 非常常见的dp的模型, 背包模型.
2. 不同类型的dp 线性dp 计数dp 等....

一个物体 有 体积 \(v_i\) 和价值 \(w_i\) 用w表示权重的意思.

每件物品仅用一次.

总体积小于等于 \(V\) 目标是让总价值最大, 最大是多少.

1. 01背包. 每个物品最多只用一次.
2. 完全背包 每件物品无限个
3. 多重背包 n个.
4. 分组背包. 每一组最多一个物品.

问背包可以装的下的情况下, 最多可以装多少物品.

闫式DP

1. 状态表示 f(i,j)

   1. 集合 所有选法: 前i个物品中, 总体积 \(\le\)j

   2. 属性 max / min / 数量.

      存储的是所有选法的最大值.

2. 状态计算

   1. 状态转移怎么来的?
   2. 集合划分. 不重 不漏.
   3. f(i,j) 不含i 和 含 i

DP优化.

背包问题

01背包问题

f(i,j) = max(f(i-1,j), f(i-1,j-v[i])+w[i])

int v[N3], w[N3];
int f[N3][N3];
int main() {
    int n = read(), m = read();
    rep(i, 1, n + 1) v[i] = read(), w[i] = read();
    rep(i, 1, n + 1) {
        rep(j, 1, m + 1) {
            f[i][j] = f[i - 1][j]; //第一个集合;
            if (v[i] <= j)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

优化成一维 看变量什么时候发生的改变.

int v[N3], w[N3];
int f[N3];
int main() {
    int n = read(), m = read();
    rep(i, 1, n + 1) v[i] = read(), w[i] = read();
    rep(i, 1, n + 1) {
        per(j, m + 1, v[i]) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

用 rep 和 per的时候也挺开心的.

完全背包问题

int v[N3], w[N3], f[N3];
int main() {
    int n = read(), m = read();
    rep(i, 0, n)v[i] = read(), w[i] = read();
    rep(i, 0, n) {
        rep(j, v[i], m + 1) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    O(f[m]);
}

多重背包问题

具体的个数.

滑动窗口最大值, 单调队列优化?

int v[N2], w[N2], f[N2][N2], s[N2];
int main() {
    int n = read(), m = read();
    rep(i, 1, n + 1)v[i] = read(), w[i] = read(), s[i] = read();
    rep(i, 1, n + 1)
        rep(j, 0, m + 1)
        for (int k = 0; k <= s[i] && k * v[i] <= j;k++)
            f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    		//直接暴力进行枚举.
    O(f[n][m]);
}

多重背包问题II

二进制优化方式. 拆分.成01背包问题.

\(s->log(s)\) 的复杂度

const int N = 25000, M = 2010;
int n, m, cnt;
int v[N], w[N], f[M];
int main() {
    n = read(), m = read();
    rep(i, 0, n) {
        int a = read(), b = read(), s = read();
        int k = 1;
        while (k <= s) {
            s -= k, cnt++;
            v[cnt] = a * k, w[cnt] = b * k;
            k *= 2;
        }
        if (s)++cnt, v[cnt] = a * s, w[cnt] = b * s;
    }
    n = cnt;
    rep(i, 1, n + 1) {
        per(j, m + 1, v[i])
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    O(f[m]);
}

分组背包问题

分组直接 多次循环就好.

每组每个都取一遍 for(每个组) for(每个体积) for(每个物品) 所以是 \(O(n^3)\)的复杂度.

const int N = N2;
int f[N], v[N][N], w[N][N], s[N];

int main() {
    int n = read(), m = read();
    rep(i, 1, n + 1) {
        s[i] = read();
        rep(j, 0, s[i]) {
            v[i][j] = read(), w[i][j] = read();
        }
    }
    rep(i, 1, n + 1)
        per(j, m + 1, 0)
        rep(k, 0, s[i]) {
        if (v[i][k] <= j)
            f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    }
    O(f[m]);
    return 0;
}

线性DP

数字三角形

最长上升子序列

最长上升子序列II

最短编辑距离

编辑距离

区间DP

石子合并

计数类DP

整数划分

数位统计DP

计数问题

状态压缩DP

蒙德里安的梦想

最短Hamilton路径

树形DP

没有上司的舞会

记忆化搜索

滑雪.

leetcode

122. 买卖股票的最佳时机 II

可以拆解成单天的交易

i买入 j卖出 p[j] - p[i]

j买入 k卖出 p[k]-p[j]

=> i买入, k卖出 p[k] - p[i]

所以直接求会上升的就好了.

int maxProfit(vector<int>& prices) {
    int res = 0;
    for(int i = 1;i<prices.size();i++){
        res+= max(prices[i]-prices[i-1],0);
    }
    return res;
}

33. 搜索旋转排序数组

二分: 找两段, 前一段满足一个性质, 后一段不满足.

二分找到以后, 直接在那一段里面搜就好了...

学一下 闫式二分吧... 这个用原来的二分不好做

55. 跳跃游戏

模拟题, 从前到后的for 可能更好.

怎么改进?

bool canJump(vector<int>& nums) {
    int l = 0;
    int step = nums[0];
    int n = nums.size();
    while(l<n){
        int next = 0;
        for(int i = l; i <= step+l && i < n;i++){
            // cout<< i <<' '<< i - step - l + nums[i]<<endl;
            next = max(next, i - step - l + nums[i]);
        }
        l = l + step; 
        step = next;
        if(next==0)if(l<n-1) return false; else break;
    }
    return true;
}

46. 全排列

这个bit set 不知道有没有其他的写法.

vector<vector<int>> res;
// state 表示第几个  (state >> 1) &1    
//   state | 1 << i;
vector<int> path; 
int n;
vector<int> num;
void dfs(int cnt,int state){
    if(cnt == n) {res.push_back(path); return;}
    for(int i = 0;i<n;i++){
        if(((state>>i)&1) == 0)  {
            path[cnt] = num[i];  
            dfs(cnt+1, state | (1 <<i));
        }
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    n = nums.size(); 
    path.resize(n);
    num = nums;
    dfs(0,0);
    return res;
}

16. 最接近的三数之和

没思路..

22. 括号生成

string 和 vector<char> 转换.

s.assgin(a.begin(), a.end());

经典的回溯?

合法的括号?:

1. 任意前缀中 左括号数量 \(\ge\) 右括号数量
2. 左右括号数量相等.

括号方案的总数 \(\frac{C_{2n}^n}{n+1}\) 卡特兰数.

// 其实可以看到, 尽量不用全局变量吧..

vector<string> ans;
vector<string> generateParenthesis(int n) {
    dfs(n, 0, 0, "");
    return ans;
}
void dfs(int& n, int lc, int rc, string seq) {
    if (lc == n && rc == n) ans.push_back(seq);
    else {
        if (lc < n) dfs(n, lc + 1, rc, seq + '(');
        if (rc < lc) dfs(n, lc, rc + 1, seq + ')');
    }
}