Shauby

分类

/ 注册

全部文章（共12篇）

题解 | #编辑距离(一)#

编辑距离(一)，动态规划，空间O(min(m,n) 尾部元素str[i]和str[j]相等，不用编辑，编辑距离就是str1[:i]到str2[:j]的编辑距离。尾部元素str[i]和str[j]不等：修改，对应的编辑距离是str1[:i]到str2[:j]的编辑距离+1。尾部元素str[i]和str...

动态规划 Python3 字符串

2022-08-23

0 297

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

矩阵最长递增路径，dfs+动态规划心路历程：看一眼题，求最长路径，欧，简单，就是从一个起点开始，用dfs把每条能走的道都走一遍，最后看所有的路中谁最长，类似于求树的深度嘛。根据这样的想法写完代码，什么，居然没有过。再瞄了一眼题，欧，原来起点不固定，那加个循环，把矩阵中所有点都遍历一边，这样总能找到...

Python3 动态规划深度优先搜索递归

2022-08-20

0 394

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

把数字翻译成字符串，动态规划，时间O(n)，空间O(1) 数组任何一个位置的数字，既可以只看当前位置组成个位数，也可以结合之前位置构成多位数。由于字母编码只在1-26之间，所以只有两种方式——只取当前数字组成1位数编码或者取当前位置+前一个位置组成两位数编码。如果以nums[:i+1]译成字符串的...

字符串数组动态规划 Python3

2022-08-16

0 262

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

最长上升子序列(一)，动态规划当前的元素，只有与之前的某个元素相接时才能组成最长上升子序列。只要之前元素比当前元素小，就可以相接，但最终与谁相接，则要看以谁结尾的上升子序列最长。相接即状态转移，若以元素i结尾的最长上升子序列长度为状态dp[i]，则它可能与之前i-1个状态相关，需遍历取满足条件的最...

动态规划数组 Python3

2022-08-16

0 345

题解 | #矩阵的最小路径和#

矩阵的最小路径和，动态规划，时间O(mn)，空间O(m) 动态规划的核心：初始状态+状态转移方程 class Solution: def minPathSum(self , matrix: List[List[int]]) -> int: m, n = len(matr...

Python3 动态规划

2022-08-15

0 244

题解 | #买卖股票的最好时机(四)#

买卖股票的最好时机(四)，动态规划，时间O(kn)，空间O(k) 买需在卖后，卖需在买后，股票的持有和卖出状态不能统一成一个状态，需要分别表示两个状态。同样的，第j次交易需要在第j-1次交易完成（买入卖出）之后，不能统一成一个操作，需要分别表示每一次操作的两个状态，那么k次交易就有2k个状态。从子问...

动态规划 Python3

2022-08-15

1 441

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

兑换零钱，动态规划，不同的初始状态 i元可以不加当前一枚硬币凑成dp[i]，也可以加当前一枚硬币凑成dp[i-coin]+1。所以新状态需要综合dp[i]和dp[i-coin]+1。如果表达式不相同，原因在于dp初始化方式不同。 class Solution: def minMoney(se...

动态规划 Python3

2022-08-14

0 323

题解 | #最长公共子串#

最长公共子串，动态规划，时间O(mn)，空间O(min(m,n)*k), k为最长公共子序列长度（超时）分析过程类似于：https://www.nowcoder.com/discuss/388075528203378688公共子串条件是：同时含有并且连续（[s1[i-1], s1[i]]与[s2[...

动态规划 Python3

2022-08-14

0 323

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

最长公共子序列，动态规划，时间O(mn)，空间O(min(m,n)*k)，k为最长公共子序列长度类似于：https://www.nowcoder.com/discuss/388075528203378688只是该问题的状态表示最长公共子序列本身而非长度。 class Solution: d...

字符串动态规划 Python3

2022-08-13

0 241

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

最长公共子序列长度，动态规划——时间O(mn)，空间O(min(m,n)) 两个字符串的公共子序列，是由两个字符串同时含有，且出现顺序一致的字符所构成的序列，核心在于同时含有和顺序一致。同时含有表示存在下标i和j使得s1[i]=s2[j]，顺序一致表示如果还存在下标p, q使得s1[p]=s2[q]...

动态规划字符串 Python3

2022-08-13

0 307