华科不平凡

分类

题解(135)

/ 注册

TA的专栏 135篇文章 8人订阅

刷遍天下无敌手

135篇文章 15888人学习

0篇文章 0人学习

全部文章（共20篇）

购物单（背包问题）来自专栏

出题者觉得0/1背包太套路了，因此给我们使了点小绊子，但是问题不大。设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多...

背包问题动态规划

2020-08-27

324 15888

最少邮票个数来自专栏

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式：当j-v[i-1]...

背包问题动态规划

2020-08-27

1 760

0/1背包问题来自专栏

“求价值最大和”，毋庸置疑，用动态规划。此类题目属于动态规划中的一个特殊类别——“背包问题”。 PS：背包问题可以分为三种—— 0/1背包问题——物品只有选/不选两种状态，求最大价值和子集背包问题——分割等和子集问题完全背包问题——物品可以无限选，求可以组合成目标值的选法设当前个数为i，当...

背包问题动态规划

2020-08-26

2 833

格雷码来自专栏

这道题目可以用普通的循环来做，也可以用动态规划来做，相比起来动态规划的思路更加清晰，代码逻辑更加紧密。当n为1时，输出0,1，n为2时，输出00,01,11,10，当n为3时，输出00,01,11,10,110,111,101,100。规律：11,10是在1,0高位上+1得到；110,111,1...

动态规划格雷码

2020-08-25

0 720

判断字符串能否由另外两个字符串相交构成来自专栏

"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：如果S1[i]==S3[i+j+1]&am...

子序列动态规划

2020-08-25

1 1114

不同子序列个数来自专栏

“求子序列个数”，毋庸置疑，这是一道动态规划题。首先定义dp[i][j]的含义：S[0..j-1]中包含T[0..i-1]的子序列个数，接下来定义状态公式：状况1: dp[i][j]=dp[i][j-1]（如果T[i-1]!=S[j-1]）状况2：dp[i][j]=dp[i][j-1] + d...

子序列动态规划

2020-08-25

2 1124

回文字符串ii（最少切割次数）来自专栏

典型的动态规划问题：对于每个位置i，以递增的方式找长度为1,3,5,7...的回文子串，然后找长度为2,4,6,8的回文子串；假设回文子串的起始位置为idx_s，结束位置为idx_e，更新dp数组的公式为dp[idx_e] = min(dp[idx_s-1] + 1, dp[idx_e]) 考...

回文动态规划

2020-08-24

2 922

三角形最短路径来自专栏

基本思想是自底向上，但是又可以细分为两种方法：空间复杂度O(n)，优点是无需修改输入空间复杂度O(1)，优点是无需辅助空间方法一 // // Created by jt on 2020/8/14. // #include <vector> using namespace std...

动态规划自底向上

2020-08-14

4 800

解码方法数来自专栏

这个动态规划有点难，因为f(i)不仅与f(i-1)有关，和f(i-2)也有关系，能想明白这一层关系着实不容易0.0 设当前的解法有f(i)种，由于s[i]和s[i - 1]的搭配方式有多种，下面分情况讨论：非法的情况，即不论怎么搭配都decode不了，返回0 合法的情况，如果只能搭配成一种，那么...

动态规划

2020-08-11

0 579

跳跃游戏II 来自专栏

符合动态规划的条件：每个状态与前一个状态有关——设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1 初始状态是已知的——刚开始几个点的f与第一个点有关然后就是实现问题了，两个循环，外循环是遍历每个点，内循环是遍历当前点的“势力范围”。 class Solution { p...

数组动态规划

2020-08-10

0 782