力扣 | 动态规划 | 动态规划在树的应用
一、96. 不同的二叉搜刮树LeetCode：96. 不同的二叉搜刮树
https://i-blog.csdnimg.cn/direct/53887d56515b4fe6b6bb86ec4b799702.png
只求个数实际上比力简朴，定义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*dp} dp=∑k=0i−1dp∗dp，即罗列左右子树的所有情况，个数的乘积就是这种情况的个数。
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp = 1, dp = 1;
for(int i = 2; i <= n; ++ i){
for(int k = 0; k < i; ++ k){
dp += dp * dp;
}
}
return dp;
}
};
二、95. 不同的二叉搜刮树 II
LeetCode：95. 不同的二叉搜刮树 II
https://i-blog.csdnimg.cn/direct/f0b8ccad20424ae19508864d882c51ba.png
这个题和之前的唯一区别就是这里维护一个真实的数，而不但仅是个数。我们仍旧可以使用相同的方法，只是这里是创建树，而且要关注值。
而且我们必要特殊留意，dp表示空树，空树并不是dp = {}而是dp={nullptr}，原因是空树为nullptr，而不是没有元素。相当于∅和{∅}的区别
以下是一种动态规划的写法，不像官解的回溯解法那么难理解：
我们将之前的dp += dp * dp改为了addTree(dp, dp, dp, k)，从只关注个数到必要创建所有情况。留意这个参数k肯定是必要的，因为这代表左子树的个数，而dp表示的是左子树的所有大概情况。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<vector<TreeNode *>> dp(n + 1);//dp表示结点个数为i 的所有可能情况
dp = {nullptr};
dp = {new TreeNode(1)};
for(int i = 2; i <= n; ++ i){
for(int k = 0; k < i; ++ k){//k表示左边有多少个，i - k - 1是右边的个数，右边以及根的大小从k + 1开始
addTree(dp, dp, dp, k);//将dp - root - dp创建 加入到dp
}
}
return dp;
}
private:
void addTree(vector<TreeNode *> & total, vector<TreeNode *> & left, vector<TreeNode *> & right, int k){//将这种情况下的所有可能树连接起来
for(int i = 0; i < left.size(); ++ i){
for(int j = 0; j < right.size(); ++ j){
TreeNode * root = new TreeNode(k + 1);
root->left = createTree(left, 0);
root->right = createTree(right, k + 1);
total.emplace_back(root);
}
}
return;
}
TreeNode * createTree(TreeNode * root, int bias){//创建树，加上偏置
if(!root) return nullptr;
TreeNode * cur = new TreeNode(root->val + bias);
cur->left = createTree(root->left, bias);
cur->right = createTree(root->right, bias);
return cur;
}
};
三、337. 打家劫舍 III
LeetCode：337. 打家劫舍 III
https://i-blog.csdnimg.cn/direct/1e733b56dfb648458ff414ac24f5bc01.png
很显着这是一个动态规划题，树形dp，怎样定义？
定义 dp为以i为根的树的最高金额？
那么，i可以被偷，也可以不被偷：
[*]dp = max(儿子的最高金额，孙子的最高金额 + i的金额） //这样就可以确保不报警的情况下，拿到最高金额
而且，我们认为dp就是对的最高金额，通过状态转移就能保证，每个都是最高金额。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode *, int> dp;
int rob(TreeNode* root) {
Getans(root);
return dp;
}
private:
void Getans(TreeNode * root){
if(!root) return;
Getans(root->left);
Getans(root->right);
int ans = root->val;
ans = max(ans, dp + dp);
int temp = root->val;
if(root->left){
temp += dp + dp;
}
if(root->right){
temp += dp + dp;
}
dp = max(temp, ans);
return;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]