xqxls

分类

二叉树技巧总结(2) 未归档(3) 题解(292)

/ 注册

TA的专栏 297篇文章 4人订阅

297篇文章 4409人学习

全部文章（共8篇）

题解 | #走网格# 来自专栏

题意整理给定一个的网格，求从起点(1,1)到终点(n,m)总共有多少不同的路劲。规定每次只能向右走和向上走，并且不能走指定的矩形区域。方法一（记忆化递归） 1.解题思路递归终止条件：横坐标在1，纵坐标也在1时，递归终止，此时只有1条路径。递归如何推进：每个位置的路径数可以由左边位置的...

Java 记忆化递归动态规划

2021-09-17

0 761

题解 | #权值最大的路径# 来自专栏

题意整理给定一个有向无环图，每个节点都有一个权值。求所有路径中，节点权值和最大的路径。方法一（记忆化递归） 1.解题思路递归终止条件：跟新完所有的节点。递归如何推进：每跟新完一个后置节点，就将当前后置节点作为新的起点进行递归。 2.代码实现 import java.util.*; ...

java 动态规划记忆化递归

2021-08-28

0 1343

题解 | #简单变向# 来自专栏

题意整理牛牛在一个3行n列的跑道上跑步。牛牛的下一步只能在原来的那一行，或者由相邻行跳转过来（不能跨行或者越界）。求牛牛从(1,1)到(3,n)有多少条不同的路径可走。方法一（记忆化递归） 1.解题思路递归终止条件：起点第1行第1列的位置肯定是可达的。递归如何推进：总共有1，2，3...

java 动态规划递归记忆化递归

2021-08-13

0 554

题解 | #又见台阶# 来自专栏

题意整理总共有n层台阶，起初牛牛在第1层。牛牛每次能跳奇数层台阶，问有多少种不同的跳法到达第n层台阶（不能踩到积水的台阶）。方法一（记忆化递归） 1.解题思路递归终止条件：只有0层或1层的时候，共1种方案，返回1。递归如何推进：当前层的方案数，需要借助之前所有相隔奇数层的方案数来计算...

java 递归记忆化递归迭代

2021-08-12

0 519

题解 | #旅行Ⅱ# 来自专栏

题意整理给定N个城市，以及每个城市的开销。一个前置城市数组，即去y城市之前必须先去x城市。求牛妹用V元最多能去多少个城市旅游。方法一（记忆化递归） 1.解题思路前置知识：假设有N个城市，每个城市的编号是，牛妹去了哪几个城市可以用一个N位二进制编码mask来表示，mask中对应位是1，则...

java 记忆化递归动态规划状压dp

2021-08-07

0 599

题解 | #牛牛恨66# 来自专栏

题意整理输入正整数。在到之间，有多少个数字不包含连续的，则输出多少。方法一（记忆化递归） 1.解题思路递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6，...

java 记忆化递归动态规划

2021-08-01

0 704

题解 | #最长回文子序列# 来自专栏

题意整理给定字符串。求这个字符串的最长回文子序列。回文序列是指，如果将原序列翻转后与原序列相等，那么这个序列是回文序列。方法一（记忆化递归） 1.解题思路递归终止条件：左边界和右边界之间只含一个元素，或只含两个元素。递归如何推进：如果左边界和右边界相等，则可以将两边分别向中间压缩一...

java 记忆化递归动态规划

2021-07-30

3 789

题解 | #二叉树的个数# 来自专栏

题意整理给定一颗节点个数为n的二叉树，二叉树中序遍历单调递增。求有多少种这样的二叉树。方法一（记忆化递归） 1.解题思路由于该二叉树中序遍历单调递增，所以可以假设n个节点的值分别为1，2，……n。这与其他单调递增的情况相比，二叉树的树形数目一样多。我们任意取一个节点为根节点，然后左子树的...

java 动态规划记忆化递归树

2021-07-28

4 958