Shauby

分类

/ 注册

全部文章（共44篇）

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

最长上升子序列(一)，动态规划当前的元素，只有与之前的某个元素相接时才能组成最长上升子序列。只要之前元素比当前元素小，就可以相接，但最终与谁相接，则要看以谁结尾的上升子序列最长。相接即状态转移，若以元素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

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

动态规划，空间O(min(m,n))，时间O(mn) 行列等价，交换之后不会影响路径数。当前位置的状态dp[j]由左边和上边的状态相加得来，而这两个状态恰好对应dp[j-1]和dp[j]。 class Solution: def uniquePaths(self , m: int, n: i...

动态规划 Python3

2022-08-12

0 311

题解 | #跳台阶#

四行解决跳台阶问题动态规划，每一个台阶对应的走法都可以由其前一个台阶和前两个台阶走法相加而得到。 class Solution: def jumpFloor(self , number: int) -> int: s0 = s1 = 1 # ...

Python3 动态规划

2022-08-12

0 0

题解 | #验证IP地址#

不借助python分割函数，纯粹的手写主要条件：字符类型，分隔符位置，字段数，字段内数的个数与范围 class Solution: def solve(self , IP: str)&nbs...

字符串 Python3

2022-08-10

0 253