xqxls

分类

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

/ 注册

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

297篇文章 4447人学习

全部文章（共28篇）

题解 | #换位# 来自专栏

题意整理给定两个同样大小的数列，现在要将第一个变为严格降序，第二个变为严格升序。可以交换两个数列同一列的元素，问最少交换多少次。如果无法交换成严格有序，返回-1。方法一（动态规划） 1.解题思路状态定义：表示当前无交换的最少交换次数，表示当前有交换的最少交换次数。状态初始化：当只有...

Java 动态规划空间压缩

2021-09-18

0 510

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

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

Java 记忆化递归动态规划

2021-09-17

0 783

题解 | #牛牛的冰激凌# 来自专栏

题意整理总共有m个冰淇淋要运输，运输车一次最多装n个，来回一趟各需t分钟。现在每个冰淇淋都有一个制作时间，求怎样运输花费时间最短，最短时间下怎样运输次数最少。方法一（动态规划） 1.解题思路状态定义:表示运输完第i个物品并且回到工厂所需要的最短时间。状态初始化:将所有状态置为Inte...

java 动态规划贪心

2021-09-10

0 538

题解 | #牛牛摇骰子# 来自专栏

题意整理给定一个一维数轴，起点在原点，每次可以向左或者向右移动0或3或7或11个单位。为了移动到目标点target，计算最少的移动次数。输入对应的target坐标集合，返回对应的移动次数集合。方法一（动态规划） 1.解题思路首先计算移动到范围内的目标点对应的最少移动次数。初始化dp...

java 动态规划数学

2021-09-09

0 547

题解 | #消息压缩# 来自专栏

题意整理有一段长度为n的消息，要将消息分成若干组，每组2个消息。第一个消息长度必须是4，第二个消息长度不能为0。求有多少种分割方法。方法一（递归） 1.解题思路递归终止条件：如果剩下的长度为0，说明正好完成分割，返回一种方案。递归如何推进：首先减去4，表示第一个消息的长度，然后第二...

java 递归动态规划

2021-09-01

0 569

题解 | #牛牛的棋盘# 来自专栏

题意整理给定的矩阵以及个点。现在要将这个点放在矩阵里，并且保证第一行，第一列，最后一行，最后一列都有点。求总共有多少种方案。方法一（动态规划） 1.解题思路初始化一个组合数组，表示在i个格子里取j个点的组合数，即。根据组合递归公式，可得：。计算出所有的组合数之后，首先取对应的所有...

java 动态规划数学

2021-08-29

0 649

题解 | #牛妹的春游# 来自专栏

题意整理给定x，y，以及若干数对[ai,bi,ci]。从中选出部分数对，使得ai数对的和不小于x，bi数对的和不小于y，求最小的ci数对的和。方法一（动态规划） 1.解题思路状态定义：dp[i][j][k]表示选择包装数为i，面包数为j，饮料数为k的情况下，最小的花费。状态初始化：不...

java 动态规划空间压缩

2021-08-28

0 598

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

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

java 动态规划记忆化递归

2021-08-28

0 1386

题解 | #牛牛的Fib序列# 来自专栏

题意整理牛牛定义了满足的一个序列，并且。求序列的第n项。方法一（数学+dp存状态） 1.解题思路根据给定的递推关系式，可以得出序列是一个周期为6的循环序列。证明：由（记为式子1）可知：（记为式子2），将式子2代入式子1，可得：，同时前移三位，可以推出，于是有：，所以是一个周期为6的序...

java 数学动态规划

2021-08-25

0 619

题解 | #牛牛的超市# 来自专栏

题意整理有n种不同的货币，给定每种货币的面值和个数。现在要将x元兑换为这些货币的组合，求总共有多少种方案。方法一（动态规划） 1.解题思路这是一个典型的背包问题，x元是背包容量，根据面值以及个数限制逐个推导出每种金额x对应的方案数。状态定义：表示i种币值下，j元的金额有多少换钱方案。...

java 动态规划状态压缩背包问题

2021-08-24

0 579