力扣 | 动态规划 | 动态规划在树的应用

一、96. 不同的二叉搜刮树

LeetCode：96. 不同的二叉搜刮树

只求个数实际上比力简朴，定义dp表示结点个数为i的二叉搜刮树的种树。（实在和记忆化搜刮+dfs差不多）
那么有                                    d                         p                         [                         i                         ]                         =                                   ∑                                       k                               =                               0                                                 i                               −                               1                                                      d                            p                            [                            i                            −                            k                            −                            1                            ]                            ∗                            d                            p                            [                            k                            ]                                       dp = \sum_{k=0}^{i - 1}{dp[i-k-1]*dp[k]}                  dp=∑k=0i−1​dp[i−k−1]∗dp[k]，即罗列左右子树的所有情况，个数的乘积就是这种情况的个数。

1. class Solution {
2. public:
3.     int numTrees(int n) {
4.         vector<int> dp(n + 1, 0);
5.         dp[0] = 1, dp[1] = 1;
7.         for(int i = 2; i <= n; ++ i){
8.             for(int k = 0; k < i; ++ k){
9.                 dp[i] += dp[k] * dp[i - k - 1];
10.             }
11.         }
12.         return dp[n];
13.     }
14. };

复制代码

二、95. 不同的二叉搜刮树 II

LeetCode：95. 不同的二叉搜刮树 II

这个题和之前的唯一区别就是这里维护一个真实的数，而不但仅是个数。我们仍旧可以使用相同的方法，只是这里是创建树，而且要关注值。
而且我们必要特殊留意，dp[0]表示空树，空树并不是dp[0] = {}而是dp[0]={nullptr}，原因是空树为nullptr，而不是没有元素。相当于∅和{∅}的区别
以下是一种动态规划的写法，不像官解的回溯解法那么难理解：
我们将之前的dp += dp[k] * dp[i - k - 1]改为了addTree(dp, dp[k], dp[i - k - 1], k)，从只关注个数到必要创建所有情况。留意这个参数k肯定是必要的，因为这代表左子树的个数，而dp[k]表示的是左子树的所有大概情况。

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     vector<TreeNode*> generateTrees(int n) {
15.         vector<vector<TreeNode *>> dp(n + 1);//dp[i]表示结点个数为i 的所有可能情况
16.         dp[0] = {nullptr};
17.         dp[1] = {new TreeNode(1)};
19.         for(int i = 2; i <= n; ++ i){
20.             for(int k = 0; k < i; ++ k){//k表示左边有多少个，i - k - 1是右边的个数，右边以及根的大小从k + 1开始
21.                 addTree(dp[i], dp[k], dp[i - k - 1], k);//将dp[k] - root - dp[i - k - 1]创建 加入到dp[i]
22.             }
23.         }
25.         return dp[n];
26.     }
27. private:
28.     void addTree(vector<TreeNode *> & total, vector<TreeNode *> & left, vector<TreeNode *> & right, int k){//将这种情况下的所有可能树连接起来
29.         for(int i = 0; i < left.size(); ++ i){
30.             for(int j = 0; j < right.size(); ++ j){
31.                 TreeNode * root = new TreeNode(k + 1);
32.                 root->left = createTree(left[i], 0);
33.                 root->right = createTree(right[j], k + 1);
34.                 total.emplace_back(root);
35.             }
36.         }
37.         return;
38.     }
39.     TreeNode * createTree(TreeNode * root, int bias){//创建树，加上偏置
40.         if(!root) return nullptr;
41.         TreeNode * cur = new TreeNode(root->val + bias);
42.         cur->left = createTree(root->left, bias);
43.         cur->right = createTree(root->right, bias);
45.         return cur;
46.     }
47. };

复制代码

三、337. 打家劫舍 III

LeetCode：337. 打家劫舍 III

很显着这是一个动态规划题，树形dp，怎样定义？
定义 dp为以i为根的树的最高金额？
那么，i可以被偷，也可以不被偷：

• dp = max(儿子的最高金额，孙子的最高金额 + i的金额） //这样就可以确保不报警的情况下，拿到最高金额
  

而且，我们认为dp就是对的最高金额，通过状态转移就能保证，每个都是最高金额。

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     unordered_map<TreeNode *, int> dp;
15.     int rob(TreeNode* root) {
16.         Getans(root);
18.         return dp[root];
19.     }
20. private:
21.     void Getans(TreeNode * root){
22.         if(!root) return;
23.         Getans(root->left);
24.         Getans(root->right);
25.         int ans = root->val;
26.         ans = max(ans, dp[root->left] + dp[root->right]);
28.         int temp = root->val;
29.         if(root->left){
30.             temp += dp[root->left->left] + dp[root->left->right];
31.         }
32.         if(root->right){
33.             temp += dp[root->right->left] + dp[root->right->right];
34.         }
36.         dp[root] = max(temp, ans);
37.         return;
38.     }
39. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。