球球了给孩子一个offer吧

题解

/ 注册

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

题解 | #牛牛的超市#

题目：定义一种新货币，有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

题解 | #k长连续子段和#

题目：给出一个n个数字的序列，求所有长度大于等于k的连续子段中，子段数字和最大可以是多少。连续子段指的是序列中一段连续的数字。子段数字和指的是子段中所有数字相加的和。关键：求长度大于等于k的最大连续子段数字和方法一：双指针左指针和右指针都置于起点，序列中的每个数字都可以作为子段的起点，当第一个数字作...

动态规划双指针

2021-08-12

0 520

题解 | #牛妹的项链#

题目关键信息：1.数组a代表项链的每颗珠子，不同的数字代表不同颜色的珠子，而且这是个环形数组，首尾是相连的2.求最长连续不重复子序列的长度方法一：暴力用list存储最长不重复子序列，因为是环形珠子，考虑首尾相连的情况，将珠子复制一份接到后面，因此循环从0到2n，每次取a[i%n],如果list中不存...

动态规划滑动窗口

2021-08-11

0 492

题解 | #取球放球#

题目：将题目换成另一个说法就是有n个数，可以对这n个数调整k次，每次只能对一个数加一或者减一，调整过程中，保持，设相邻两数的差的平方中的最大值为x，求调整k次后，x最小是多少方法一：贪心最多调整k次，因此枚举k次在开始一轮调整前，先用一个dst数组存储相邻两数的差值，,然后找出相邻两数差值的平...

动态规划贪心

2021-08-11

0 528

题解 | #递增数组#

题目描述：牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？关键点：每次选择一个连续的区间，区间的数一次性加1数组元素必须严格单调递增，不能出现元素相等的情况方法一：贪心要使得整个数组严格单调递增，就需要数组中每个局...

动态规划数组贪心

2021-08-07

0 1331

题解 | #单帧操作#

题目：给定n个数字的序列，对位置i进行一次操作将使得都变成特别的，对位置0进行操作将使得和都变成对位置进行操作将使得和都变成并且操作过位置i之后，位置0到i都不能再操作设最多可以操作k(k≤n)次，最后得到的整个序列的总和最大可以是你需要求出方法一：四维动态规划定义：表示第个位置进行第j次操作值为的...

动态规划

2021-08-06

0 604

题解 | #牛妹的蛋糕#

题目描述众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？这道题是典型的猴子吃桃问题...

递归动态规划

2021-08-03

0 685

题解 | #牛能和牛可乐的礼物#

题目关键信息：给定一个数组，将数组分成两个部分，使得这两部分的和的差最小方法一：动态规划“数组”，“求最优值”显然这道题可以用动态规划解决，这是0-1背包的变形类题目，求数组两部分的和的差的最小值，假设数组的总和为，部分一的和为，部分二的和为，那么增加，就减小,减小,就增加,,因此背包的最大容量是...

动态规划

2021-08-02

0 602

题解 | #牛妹的礼物#

题意描述：有NxM大小的矩阵，从左上角走到右下角，只能向右，下，右下走，求到达右下角的最短带权路径长度方法一：动态规划采用递推的方式,定义一个二维数组，显然，的值就是从左上角走到的最短路径，要求从左上角到右下角的最短路径就是求的值状态转移方程： import java.util.*; p...

动态规划递归

2021-08-01

0 445