树形动态规划

树形动态规划

树形动态规划与线性动态规划没有本质区别
其实只是套在深度优先遍历里的动态规划(在DFS的过程中实现DP)
子问题就是“一棵子树”, 状态一般表示为“以x为根的子树”, 决策就是"x的子结点”

复杂的题目可以在此基础上增加更多与题目相关的状态、决策

实战

337.打家劫舍III
https://leetcode.cn/problems/house-robber-iii/

f[x,0]表示以x为根的子树，在不打劫x的情况下，能够盗取的最高金额
f[x,1]表示以x为根的子树，在打劫x的情况下，能够盗取的最高金额

目标: max(f[root,0], f[root, 1])

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        f = new HashMap<TreeNode, int[]>();
        f.put(null, new int[]{0, 0});
        dfs(root);
        return Math.max(f.get(root)[0], f.get(root)[1]);
    }

    private void dfs(TreeNode root) {
        if(root == null) return;
        f.put(root, new int[2]);
        dfs(root.left);
        dfs(root.right);
        f.get(root)[0] = 
            Math.max(f.get(root.left)[0], f.get(root.left)[1]) +
            Math.max(f.get(root.right)[0], f.get(root.right)[1]);
        f.get(root)[1] = 
            f.get(root.left)[0] + f.get(root.right)[0] + root.val;
    }

    HashMap<TreeNode, int[]> f; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    unordered_map <TreeNode*, int> f, g;

    void dfs(TreeNode* node) {
        if (!node) {
            return;
        }
        dfs(node->left);
        dfs(node->right);
        f[node] = node->val + g[node->left] + g[node->right];
        g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]);
    }

    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root], g[root]);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

匈牙利算法
参考引用
https://leetcode.cn/circle/article/SCLpQf/
https://zhuanlan.zhihu.com/p/393028740

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习