动态规划入门

原题单链接：https://rentry.org/2f76axt4

见到很有意思的问题 : 以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。(看到一位知乎的大佬说的, 深有感悟~)

动态规划 就是 : 给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法.

那么我们今天就来带给大家 新手入门动态规划的正确方法!

记忆化搜索 = 暴力dfs + 记录答案

动态规划入门思路: dfs暴力 — 记忆化搜索 — 递推

1dfs > 2记忆化搜索 > 3逆序递推 > 4顺序递推 > 5优化空间 !

递归的过程:

“递” 的过程是: 分解子问题的过程;

“归” 的过程才是: 产生答案的过程;

“递” – 自顶向下, “归” – 自底向上 ，其中 “底” 是 递归搜索树 的底

写出递推公式的方法:

递推的公式 = dfs 向下递归的公式

递推数组的初始值 = 递归的边界

例题

acwing821.跳台阶 \或者\ P1255. 数楼梯

跳台阶

f[i]=f[i-1]+f[i-2]，使用十进制字符串加法支持 P1255 的大整数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<string> f(max(2,n+1)); f[0]=f[1]="1";
    auto add=[](string a,string b) { string c; int carry=0; reverse(a.begin(),a.end()); reverse(b.begin(),b.end());
        for(int i=0;i<(int)max(a.size(),b.size()) || carry;++i) {
            int v=carry+(i<(int)a.size()?a[i]-'0':0)+(i<(int)b.size()?b[i]-'0':0); c+=char('0'+v%10); carry=v/10;
        } reverse(c.begin(),c.end()); return c; };
    for(int i=2;i<=n;++i) f[i]=add(f[i-1],f[i-2]); cout << f[n] << '\n';
}

打家劫舍

相邻房屋不能同时选择，转移为 f[i]=max(f[i-1],f[i-2]+a[i])。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; cin >> T;
    while(T--) { int n; cin >> n; long long prev=0,cur=0;
        while(n--) { long long x; cin >> x; long long next=max(cur,prev+x); prev=cur; cur=next; }
        cout << cur << '\n'; }
}

数字三角形

自底向上递推，支持负数节点。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<vector<int>> a(n+1,vector<int>(n+2));
    for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) cin >> a[i][j];
    vector<int> f(n+2);
    for(int i=n;i>=1;--i) for(int j=1;j<=i;++j) f[j]=a[i][j]+max(f[j],f[j+1]);
    cout << f[1] << '\n';
}

01 背包：暴力、记忆化与递推

#include <bits/stdc++.h>
using namespace std;

int n,m; vector<int> v,w; vector<vector<int>> mem;
int brute(int x,int cap) {
    if(x==n) return 0;
    int ans=brute(x+1,cap);
    if(cap>=v[x]) ans=max(ans,brute(x+1,cap-v[x])+w[x]); return ans;
}
int dfs(int x,int cap) {
    if(x==n) return 0;
    int &ans=mem[x][cap]; if(ans!=-1) return ans;
    ans=dfs(x+1,cap); if(cap>=v[x]) ans=max(ans,dfs(x+1,cap-v[x])+w[x]); return ans;
}
int main() {
    cin >> n >> m; v.resize(n); w.resize(n); for(int i=0;i<n;++i) cin >> v[i] >> w[i];
    mem.assign(n,vector<int>(m+1,-1));
    vector<int> f(m+1);
    for(int i=0;i<n;++i) for(int j=m;j>=v[i];--j) f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout << f[m] << '\n'; // 也可以用 dfs(0,m)；brute 仅用于小数据
}