ToB企服应用市场:ToB评测及商务社交产业平台

标题: 力扣 | 动态规划 | 动态规划在树的应用 [打印本页]
作者: 笑看天下无敌手    时间: 2024-8-15 23:04
标题: 力扣 | 动态规划 | 动态规划在树的应用
一、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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4