网站tdk优化,网站备案好还是不备案好,电商软件开发费用,国内最新新闻事件摘抄【问题描述】[中等] 【解答思路】
1. 动态规划
第 1 步#xff1a;状态定义 dp[node][j] #xff1a;这里 node 表示一个结点#xff0c;以 node 为根结点的树#xff0c;并且规定了 node 是否偷取能够获得的最大价值。
j 0 表示 node 结点不偷取#xff1b; j 1 表示…【问题描述】[中等] 【解答思路】
1. 动态规划
第 1 步状态定义 dp[node][j] 这里 node 表示一个结点以 node 为根结点的树并且规定了 node 是否偷取能够获得的最大价值。
j 0 表示 node 结点不偷取 j 1 表示 node 结点偷取。 第 2 步 推导状态转移方程 根据当前结点偷或者不偷就决定了需要从哪些子结点里的对应的状态转移过来。
如果当前结点不偷左右子结点偷或者不偷都行选最大者 如果当前结点偷左右子结点均不能偷。 状态转移方程的表述有点复杂请大家直接看代码。
第 3 步 初始化 一个结点都没有空节点返回 0对应后序遍历时候的递归终止条件
第 4 步 输出 在根结点的时候返回两个状态的较大者。
第 5 步 思考优化空间 优化不了。 时间复杂度O(N) 空间复杂度O(N)
public class Solution {// 树的后序遍历public int rob(TreeNode root) {int[] res dfs(root);return Math.max(res[0], res[1]);}private int[] dfs(TreeNode node) {if (node null) {return new int[]{0, 0};}// 分类讨论的标准是当前结点偷或者不偷// 由于需要后序遍历所以先计算左右子结点然后计算当前结点的状态值int[] left dfs(node.left);int[] right dfs(node.right);// dp[0]以当前 node 为根结点的子树能够偷取的最大价值规定 node 结点不偷// dp[1]以当前 node 为根结点的子树能够偷取的最大价值规定 node 结点偷int[] dp new int[2];dp[0] Math.max(left[0], left[1]) Math.max(right[0], right[1]);dp[1] node.val left[0] right[0];return dp;}
}
2. 递归
使用爷爷、两个孩子、4 个孙子来说明问题 首先来定义这个问题的状态 爷爷节点获取到最大的偷取的钱数呢
首先要明确相邻的节点不能偷也就是爷爷选择偷儿子就不能偷了但是孙子可以偷二叉树只有左右两个孩子一个爷爷最多 2 个儿子4 个孙子 根据以上条件我们可以得出单个节点的钱该怎么算 4 个孙子偷的钱 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多就当做当前节点能偷的最大钱数。这就是动态规划里面的最优子结构 由于是二叉树这里可以选择计算所有子节点
4 个孙子投的钱加上爷爷的钱如下 int method1 root.val rob(root.left.left) rob(root.left.right) rob(root.right.left) rob(root.right.right) 两个儿子偷的钱如下 int method2 rob(root.left) rob(root.right); 挑选一个钱数多的方案则 int result Math.max(method1, method2);
2.1暴力递归
public int rob(TreeNode root) {if (root null) return 0;int money root.val;if (root.left ! null) {money (rob(root.left.left) rob(root.left.right));}if (root.right ! null) {money (rob(root.right.left) rob(root.right.right));}return Math.max(money, rob(root.left) rob(root.right));
}
2.2 记忆化递归 针对2.1中速度太慢的问题经过分析其实现我们发现爷爷在计算自己能偷多少钱的时候同时计算了 4 个孙子能偷多少钱也计算了 2 个儿子能偷多少钱。这样在儿子当爷爷时就会产生重复计算一遍孙子节点。
于是乎我们发现了一个动态规划的关键优化点
我们这一步针对重复子问题进行优化我们在做斐波那契数列时使用的优化方案是记忆化但是之前的问题都是使用数组解决的把每次计算的结果都存起来下次如果再来计算就从缓存中取不再计算了这样就保证每个数字只计算一次。 由于二叉树不适合拿数组当缓存我们这次使用哈希表来存储结果TreeNode 当做 key能偷的钱当做 value
public int rob(TreeNode root) {
//hashmap 记忆化HashMapTreeNode, Integer memo new HashMap();return robInternal(root, memo);
}public int robInternal(TreeNode root, HashMapTreeNode, Integer memo) {if (root null) return 0;if (memo.containsKey(root)) return memo.get(root);int money root.val;if (root.left ! null) {money (robInternal(root.left.left, memo) robInternal(root.left.right, memo));}if (root.right ! null) {money (robInternal(root.right.left, memo) robInternal(root.right.right, memo));}int result Math.max(money, robInternal(root.left, memo) robInternal(root.right, memo));///memo.put(root, result);return result;
}
【总结】
1. 动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2.递归 递推公式要找准 后用记忆化搜索优化 这题不能用BFS层次遍历不符合题解
转载链接https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/ 转载链接https://leetcode-cn.com/problems/house-robber-iii/solution/shu-xing-dp-ru-men-wen-ti-by-liweiwei1419/
