训练dp的一个不错的方式

dp讲义

线性DP

[x] 单串：最长上升子序列 leetcode300
[x] 双串：最长公共子序列 leetcode1143
[x] 数字三角形 leetcode120
[x] 最大子段和 leetcode53
[x] 最大子段积 leetcode152
[x] 俄罗斯套娃信封 leetcode354
[x] 打家劫舍 leetcode198,213
[x] 编辑距离 leetcode72
[x] 正则表达式匹配 leetcode12
[x] 把数字翻译成字符串面试题46 扔鸡蛋 leetcode887 买卖股票 leetcode121,122,123,188,309,714 通配符 leetcode44

区间DP

[x] 最长回文子序列 leetocde516 回文子序列个数 leetcode730
[x] 最优三角形剖分 leetcode1039 刷串问题 leetcode664
[x] 戳气球 leetcode312

记忆化递归

[x] 矩阵中的最长上升路径 leetcode329

背包DP

[x] leetcode 416, 494(01背包)
[x] leetcode 518, 322(完全背包)
[x] leetcode 474(二维费用背包)

树形DP

[x] 最大权路径 leetcode124
[x] 树的直径 leetcode543,1245 最大二叉搜索子树 leetcode333 树形依赖 leetcode337

状态压缩DP

leetcode 526,464,935,1349

数位DP

leetcode902,1015,233

计数型DP

[x] leetcode 62, 63
[x] leetcode 22, 96(卡特兰数) leetcode1259 (借助卢卡斯定理求大组合数模质数的结果)

递推型DP

leetcode 50, 70,372,509,935,957, 1137

概率型DP

leetcode 808, 837

博弈型DP

策梅洛定理，SG定理翻转游戏(leetcode293,294) Nim游戏(leetcode292) 石子游戏(leetcode877,1040) 井字游戏(leetcode348,794,1275)

LeetCode 1245. Tree Diameter 树的直径

本题是vip题，无奈，只能自己手搓了

就是求多叉树的直径

题解

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

class Solution {
public:
    vector<vector<int>> g;
    int res = 0;

    // 返回以u为跟的最长的一条路
    int dfs(int u, int fa) {
        int mx1=0, mx2=0;
        for (int i=0; i<g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa) continue;
            int l = dfs(v, u);
            if (l > mx1) {
                mx2 = mx1;
                mx1 = l;
            } else if (l > mx2) {
                mx2 = l;
            }
        }
        res = max(res, mx1+mx2+1);
        return mx1+1;
    }

    int treeDiameter(vector<vector<int>>& edges) {
        int len = edges.size();
        g.resize(len+5);
        for (int i=0; i<=len; i++) g[i].clear();
        res = 0;

        for (auto edge : edges) {
            int x = edge[0], y = edge[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        dfs(0, -1);
        return res - 1;
    }
};

int main() 
{
    freopen("1245.txt", "r", stdin);
    int n, m;
    // m条边
    vector<vector<int>> edges;
    Solution s;
    while (cin >> m) {
        vector<vector<int>> edges;
        for (int i=0; i<m; i++) {
            int x, y;
            cin >> x >> y;
            edges.push_back({x, y});
        }
                int res = s.treeDiameter(edges);
        cout << res << endl;
    }
}

Draymonders / Code-Life

DP题目汇总 #40