球球了给孩子一个offer吧

题解

/ 注册

全部文章 / 题解（共7篇）

题解 | #权值最大的路径#

题目：给出一个有向无环图，规定路径是单向且小序号指向大序号，每个节点都有权值。在图上求一条路径使得经过的节点权值和最大，输出路径方法一：递归先构建邻接矩阵存储每个结点的邻接结点记录以每个结点为结尾结点时的路径权值和以及路径，路径权值和存储在w数组中，对应路径存储在path数组中，找出路径权值和...

递归记忆化搜索

2021-09-04

0 682

题解 | #牛牛的超市#

题目：定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？方法一：动态规划这是背包问题的变形，我们可以定义dp[i]...

记忆化搜索动态规划

2021-08-21

0 615

题解 | #简单变向#

题目：矩阵大小为3xn，以(1,1)为起点可以向右走，右上对角线走，右下对角线走（不能出界），有些位置设置了路障，走不了，求出从(1,1)到(3,n)的路径数量方法一：记忆化递归可以用自顶向下的递归解决初始化路障数组，遇到路障直接返回0，为了避免重复计算，初始化记忆数组每个位置为0，用记忆数组记录...

记忆化搜索递归动态规划

2021-08-14

0 404

题解 | #又见台阶#

题目：台阶一共有n层，有一些台阶上有积水。牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。已知有m个台阶上有积水。请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第n层，则答案为0。为了防止答案过大，答案对1e9+7取模。方法一...

记忆化搜索递归

2021-08-13

0 469

题解 | #切割成本#

题目描述：将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。示例输入：20,[2,5,10,18]返回值：45说明：线段长为20，切割点为[2,5,10,18]。第一种方案：1.先切开第一个点，成本为2+18=202.切开第二个点，成本...

区间dp 记忆化搜索递归

2021-08-04

0 511

题解 | #不相邻最大子序列和#

描述给你一个n（1≤n≤10^5），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。示例输入：3,[1,2,3]返回值：4说明：有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4 这道题本质上是“...

记忆化搜索递归动态规划

2021-07-28

0 573

题解 | #矩阵最长递增路径#

描述给定一个矩阵，矩阵内所有数均为非负整数。求一条路径，该路径上所有数是递增的。这个路径必须满足以下条件：1、对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。2、你不能走重复的单元格。即每个格子最多只能走一次。示例输入：[[1,2,3],[4,5,6...

记忆化搜索拓扑排序

2021-07-20

0 997