Open17's Blog

Appearance

动态规划

前言 ​

dpi的定义是一些元素算得的结果

时间复杂度计算: 状态个数*单个状态所需的时间

转为递推?

  • 确定边界
  • 自树底向上

简单DP ​

01背包 ​

cpp
// https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/
// 灵板
// 恰好满足
vector<int> f(target + 1, INT_MIN);
f[0] = 0;
int s = 0;
for (int x : nums) {
    // 上界小优化，s表示最大可能和（重量
    // 不过转移最值时可能有个注意事项（详见lastStoneWeightII）
    s = min(s + x, target);
    for (int j = s; j >= x; j--) {
        f[j] = max(f[j], f[j - x] + 1);
    }
}

完全背包 ​

cpp
// https://leetcode.cn/problems/coin-change/description/
// 最小值
vector<int> f(amount+1,0x3f3f3f);
f[0]=0;
for(auto c:coins){
    for(int i=c;i<=amount;i++){
        f[i]=min(f[i],f[i-c]+1);
    }
}

LCS ​

cpp
// https://leetcode.cn/problems/longest-common-subsequence/
int n=text1.size(),m=text2.size();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(text1[i]==text2[j])f[i+1][j+1]=f[i][j]+1;
        else f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
    }
}

数位DP ​

cpp
// https://leetcode.cn/problems/numbers-with-repeated-digits/solutions/1748539/by-endlesscheng-c5vg/
// 0x3f v1.0
class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        auto s = to_string(n);
        int m = s.length(), memo[m][1 << 10];
        memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
        function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int {
            if (i == m)
                return is_num; // is_num 为 true 表示得到了一个合法数字
            if (!is_limit && is_num && memo[i][mask] != -1)
                return memo[i][mask];
            int res = 0;
            if (!is_num) // 可以跳过当前数位
                res = f(i + 1, mask, false, false);
            int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
            for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
                if ((mask >> d & 1) == 0) // d 不在 mask 中
                    res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
            if (!is_limit && is_num)
                memo[i][mask] = res;
            return res;
        };
        return n - f(0, 0, true, false);
    }
};

树形DP ​

树的直径 ​

cpp
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n=len(parent)
        g=[[] for _ in range(n)]
        for i in range(1,n):
            g[parent[i]].append(i)
        ans=0
        def f(root):
            if root>=n:
                return 0
            res=0
            for son in g[root]:
                v=f(son)+1
                nonlocal ans
                if s[root]!=s[son]:
                    ans=max(ans,v+res)
                    res=max(res,v)
            return res
        f(0)
        return ans+1

换根DP ​

两次扫描，换根dp

思考根转移对于整体答案变化的贡献

cpp
// https://leetcode.cn/problems/sum-of-distances-in-tree/description/
// 灵板
class Solution {
public:
    int N;
    vector<int> ans;
    vector<int> tr_n;
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        N=n;
        vector<int> g[n];
        ans.resize(n,0);
        tr_n.resize(n);
        for (auto &e: edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        dfs(g,0,-1);
        dp(g,0,-1);
        return ans;
    }
    int dfs(vector<int> g[],int node,int fa){
        tr_n[node]=1;
        int p=1;
        for(auto son:g[node]){
            if(son==fa)continue;
            p+=dfs(g,son,node);
            tr_n[node]+=tr_n[son];
        }
        if(fa!=-1)ans[0]+=p;
        return p;
    }
    void dp(vector<int> g[],int node,int fa){
        for(auto son:g[node]){
            if(son==fa)continue;
            ans[son]=ans[node]+N-2*tr_n[son];
            dp(g,son,node);
        }
    }
};