摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10952人学习

全部文章（共87篇）

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

思路：题目的主要信息：一个N个城市，A数组中记录的是访问每个城市所需的花费，V是初始所有的总预算如果同时访问了两个城市，需要满足List中Point记录的先后顺序求满足预算条件下，最多访问的城市数方法一：暴力法（超时）具体做法：利用next_permutation函数对1-N个城市进行...

递归动态规划数组次序

2021-08-03

0 537

题解 | #切割成本# 来自专栏

思路：题目的主要信息：给定一个一个长为的线段，和一系列切割点切割点的成本等于切割后产生的两段线段的和要求所有切割点的最小切割成本和方法一：动态规划具体做法：我们可以用动态规划解决这个问题，创建辅助数组dp，其中用表示之间（前闭后开）的切割点的最小成本，只要完善dp数组，最后的就是...

动态规划数组切割成本

2021-08-02

0 546

题解 | #取球放球# 来自专栏

思路：题目的主要信息：一共n个箱子，每个箱子有一定容量和一定初始球个数进行k次操作，每次操作对某一个箱子中的球进行加1或者减1 求k次操作之后要使任意相邻箱子球数差的平方的最大值达到最小。方法一：贪心具体做法：利用贪心思想，利用一个辅助数组每次操作前记录相邻两个数组之差，并找到差的最大值...

二分法动态规划贪心数组

2021-08-02

0 540

题解 | #牛妹的面试# 来自专栏

思路：题目的主要信息：凸子序列：对于子序列中的,使得所有单调递增或单调递减序列也算凸序列单独一个数是长度为1的凸序列序列数大于0，不用考虑特殊情况求一个序列中的最长凸子序列长度其实这就是两个最长递增子序列问题的叠加，从左往右是找一个最长递增子序列，从右往左也是找一个最长递增子序列...

动态规划数组凸子序列最长递增子序列二分法

2021-08-02

0 540

题解 | #牛妹的礼物# 来自专栏

思路：题目的主要信息：矩阵不为空，且矩阵中的内容非负数总体上要从矩阵的左上角到右下角，每次可以选择向下、向右、向右下三个方向路过矩阵每个格子中的数累加，求最短路径和事实上，这道题就是一个求矩阵最短路径和的问题，只不过它是有三个方向可以选择。方法一：递归（超时）具体做法：容易想到的是，...

动态规划空间记忆递归数组矩阵矩阵最小路径和

2021-07-31

0 568

题解 | #牛能和牛可乐的礼物# 来自专栏

思路：题目的主要信息：给定一串数组，将数组分为两部分要使两部分各自的和相差最小两部分的值越接近于总和的一半，相差越小。方法一：动态规划（01背包）具体做法：依据上面提到的性质，我们可以将这个问题看成一个01背包问题：背包容量为总和的一半，因此我们要装两部分，然后依次遍历数组，利用动态规...

动态规划空间记忆递归 01背包

2021-07-31

0 584

题解 | #单帧操作# 来自专栏

思路：题目的主要信息：给一串数组，每次找到一个位置进行一次操作：将该位置前后一个数及本身改为三者中的最大值一共进行n次操作，每次操作需要找到改变后使数组和最大那个位置来改变方法一：暴力解法（超时）具体做法：利用二进制掩码的特性，枚举所有位置选择或是不选择的组合（相当于n次操作，选择的位置...

动态规划 bfs 数组

2021-07-30

0 510

题解 | #一样的水# 来自专栏

思路：题目的主要信息：数组a是初始时水桶里的水数组p是每次询问后，要求水桶中水相同的水桶数量一共是q次查询，每次需要找到使水桶中拥有相同水量的水桶数量达到p中要求的最少花费，即每次加水量最少方法一：动态规划+前缀和具体做法：我们用（下标1开始）表示前i个数的和。对于某一次查询，我们要求...

数组动态规划查找迭代前缀和

2021-07-30

0 580

题解 | #牛妹的蛋糕# 来自专栏

思路：题目的主要信息：每天吃掉蛋糕总数的1/3，再额外吃1个吃到第n天还剩下1个蛋糕，问最开始总共有多少蛋糕这是一个数学问题，可以用递归、动态规划、迭代处理。方法一：递归具体做法：第n天还剩下1一个蛋糕，那么总蛋糕数就是n-1的子问题+1的3/2，可以写出如下递归： class Sol...

递归迭代动态规划数学模拟

2021-07-29

0 535

题解 | #最大子三角形# 来自专栏

思路：题目的主要信息：从一个六边形的01矩阵中找到全1的三角形，且要找边长最大的一个其中六边形矩阵的数据以vector数组的形式给出因为给出的数据是一维的，现在首要的难题的是将一维数组表示的六边形矩阵装入二维矩阵。仔细观察边长为的六边形矩阵，一共是行，最长是列。因此我们建立一个这样的矩阵保存...

最大子三角形六边形数组动态规划迭代

2021-07-29

1 581