当前位置:网站首页>Looting iii[post sequence traversal and backtracking + dynamic planning]
Looting iii[post sequence traversal and backtracking + dynamic planning]
2022-07-06 19:13:00 【REN_ Linsen】
Backtracking joint dynamic programming
Preface
For tree problems , There is Preface and DFS/ Medium order and balanced binary tree / Postscript and backtracking / Sequence and BFS. For home raiding , It is a classic dynamic programming problem , When a linear array is transformed into a branched tree structure , How should the state be transferred from two branches ?
Can cooperate with backtracking , Get the node savings of the two branches of the left and right children , According to actual needs , Choose to save money .
One 、 raid homes and plunder houses III
When the state transition doesn't think carefully , Encountered tree structure .
Two 、 to flash back + Dynamic programming
package everyday.tree;
public class Rob {
// Use backtracking to cooperate with dynamic programming .
public int rob(TreeNode root) {
int[] r = order(root);
return Math.max(r[0], r[1]);
}
private int[] order(TreeNode root) {
if (null == root) return new int[]{
0, 0};
int[] l = order(root.left);
int[] r = order(root.right);
// Root selection , You can only choose the money saved by the deeper node .
int first = root.val + l[0] + r[0];
// Don't choose the root , This is worth considering , In the left child of the root and the next layer, you can choose any one , After all, it won't be next to the root , The same goes for the right side .
int second = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{
second, first};
/* Binary tree problem : Preorder traversal and DFS; Middle order traversal and balanced binary tree ; Post order traversal and backtracking ; Sequence traversal and BFS; */
}
// 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;
}
}
}
summary
1) The basis of the tree problem , is , Preface and DFS/ Middle order and balanced binary / Postscript and backtracking / Sequence and BFS.
2) State transition of Dynamic Planning , It is a place worthy of careful consideration .
reference
边栏推荐
- ACTF 2022圆满落幕,0ops战队二连冠!!
- 史上超级详细,想找工作的你还不看这份资料就晚了
- Help improve the professional quality of safety talents | the first stage of personal ability certification and assessment has been successfully completed!
- tensorflow和torch代码验证cuda是否安装成功
- Handwritten online chat system (principle part 1)
- 应用使用Druid连接池经常性断链问题分析
- RedisSystemException:WRONGTYPE Operation against a key holding the wrong kind of value
- R language ggplot2 visualization: use ggviolin function of ggpubr package to visualize violin diagram
- The dplyr package of R language performs data grouping aggregation statistical transformations and calculates the grouping mean of dataframe data
- C#/VB. Net to add text / image watermarks to PDF documents
猜你喜欢
AUTOCAD——中心线绘制、CAD默认线宽是多少?可以修改吗?
ACTF 2022圆满落幕,0ops战队二连冠!!
How are you in the first half of the year occupied by the epidemic| Mid 2022 summary
抽象类与抽象方法
倒计时2天|腾讯云消息队列数据接入平台(Data Import Platform)直播预告
Php+redis realizes the function of canceling orders over time
能源行业的数字化“新”运维
Video based full link Intelligent Cloud? This article explains in detail what Alibaba cloud video cloud "intelligent media production" is
C language daily practice - day 22: Zero foundation learning dynamic planning
Reptiles have a good time. Are you full? These three bottom lines must not be touched!
随机推荐
Intelligent supply chain management system solution for hardware and electromechanical industry: digital intelligent supply chain "creates new blood" for traditional industries
Airiot IOT platform enables the container industry to build [welding station information monitoring system]
Mathematics in machine learning -- common probability distribution (XIII): Logistic Distribution
Solution of intelligent management platform for suppliers in hardware and electromechanical industry: optimize supply chain management and drive enterprise performance growth
主从搭建报错:The slave I/O thread stops because master and slave have equal MySQL serv
Detailed idea and code implementation of infix expression to suffix expression
抽象类与抽象方法
Interview assault 63: how to remove duplication in MySQL?
[translation] a GPU approach to particle physics
Crawling data encounters single point login problem
手写一个的在线聊天系统(原理篇1)
RedisSystemException:WRONGTYPE Operation against a key holding the wrong kind of value
多线程基础:线程基本概念与线程的创建
Openmv4 learning notes 1 --- one click download, background knowledge of image processing, lab brightness contrast
How to improve website weight
Leetcode topic [array] - 119 Yang Hui triangle II
How are you in the first half of the year occupied by the epidemic| Mid 2022 summary
Estimate blood pressure according to PPG using spectral spectrum time depth neural network [turn]
How word displays modification traces
Druid 数据库连接池 详解