心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #最长上升子序列(一)#

如何体现上升的逻辑？定义DP数组存放的是以当前位置i结尾的子序列中的最长上升子序列长度，此时可以在0到i的所有子数组中寻找上升子序列，因为是0到i的子数组，所以保证了j<i，所以当arr[j]<arr[i]时，说明i是上升子序列的一部分，则此时以arr[i]结尾的上升子序列长度为dp[i...

2023-03-28

0 258

题解 | #兑换零钱(一)#

背包问题此题可视为背包问题，要兑换的钱数aim为背包容量，arr为各个物品的价值，最少需要arr中的几件物品才能装满背包。如何转换为动态规划思路：DP数组应该存放什么？题目要求的是最少需要多少张arr中的货币才能组成aim的钱数，可以自顶向下分析，组成aim-1的钱数最少需要多少张货币，... ，组...

2023-03-27

0 249

题解 | #把数字翻译成字符串#

题意理解数组中的所有数字都必须参与译码，并且数字范围是[1, 26]。两位数组合应该在[10, 26]之间，并且是十位数，如02的组合也是无效的。0作为单数字译码肯定是无效的，0和其他数字组合作为译码时，只有10和20这个组合可以在[10, 26]范围内译码，其他情况都是无效的，此时这个数组就无法译...

2023-03-27

0 275

题解 | #不同路径的数目(一)#

动态规划思路题目所求的是左上角到右下角的所有路径数量，那么中间状态为左上角到地图中任意方格的所有路径数量，由于机器人只能往下或者往右移动，因此任意方格的路径数量只跟上一方格和左一方格的路径数量有关，按照这两个方格状态转移到最终方格的路径数量即可。最小子问题当地图大小为1xn或者mx1时，所有方格的路...

2023-03-27

0 450

题解 | #最长公共子串#

最长公共子串和最长公共子序列的区别两个字符串的“最值”问题，可以使用二维DP的思路。之前解的最长公共子序列不要求字符之间连续，只需要相对位置不变即可，但是最长公共子串要求所有字符连续。如何在代码中体现字符连续这一逻辑呢？这需要改变二维DP数组的定义，之前的最长公共子序列的二维DP数组存放的是s1字符...

2023-03-26

0 0

题解 | #最长公共子序列(二)#

二维DP问题需要维护一个二维DP表，行和列分别表示两个字符串的各个字符位置，表中的值表示两个字符串在当前位置的最长公共子序列的长度。两个字符串的当前状态为s1的第i个字符和s2和第j个字符前的子串的最长公共子序列，这个最长公共子序列由这两个字符串的前一位字符前的子串，即s1的第i-1个字符和s2的第...

2023-03-26

0 0

题解 | #最小花费爬楼梯#

动态规划思想将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。DP数组应该保存什么？题目...

2023-03-26

0 0

题解 | #斐波那契数列#

方法一：递归（我的第一想法）如何计算递归的时间复杂度？首先计算子问题个数：递归中的子问题个数即为递归树中节点的总数。二叉树的节点总数为指数级别，所以子问题个数为O(2n)然后计算解决一个子问题的时间：在本算法中没有循环，只有一个加法操作，所以时间为O(1)综上，这个算法的时间复杂度为二者相乘，为O(...

2023-03-25

0 0