fred-coder

分类

题解(149)

/ 注册

TA的专栏 32篇文章 0人订阅

32篇文章 625人学习

全部文章（共28篇）

题解 | #回文子串的数量#

由于字符串长度 <= 1000, 可直接采用暴力解法 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param str string字符串 # @return int整型 # class Solution: def Substrin...

Python3 数组字符串动态规划

2022-03-20

0 415

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

动态规划,二维 dp, 两个维度一是天数，二是持有状态; dp[i][0] 表示第 i 天未持有的最大收益, dp[i][1] 表示第 i 天持有的最大收益转移方程为: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] ...

Python3 动态规划数组

2022-03-06

0 545

题解 | #最少的完全平方数#

dp 问题, 设置 dp[i] 表示能组成 i 的最少完全平方数, dp[0] = 0, dp[i] = min(dp[i - j * j] + 1, dp[i]) j < i dp[i - j * j] 表示上一个组成完全平方数的最少值,因为每个正数都可以是完全平方数(1 + 1 + ......

Python3 动态规划

2022-02-28

0 453

题解 | #几步可以从头跳到尾#

由于数组的长度为 10 ** 5, 双重循环会超时,利用一维 dp, 设置 dp[i] 表示跳至 i 阶时最小的步数, 则 dp[i] = dp[j] + 1, j < i and j 从距离 i 最远的点跳过来, 即 A[j] 在 A[j:i] 中最大(最接近 i); 初始 dp = [...

Python3 动态规划数组

2022-02-24

0 391

题解 | #最长回文子序列#

二维 dp 问题; 设置二维 dp， dp[i][j] 表示以 i 为开始, j 为结束的回文子序列的最长长度; 当 s[i] = s[j] 时, dp[i][j] 由 dp[i + 1][j - 1] 转移过来 + s[i] 和 s[j] 的长度 2 当 s[i] != s[j] 时, dp[...

Python3 字符串动态规划

2022-02-20

5 534

题解 | #跳台阶扩展问题#

动态规划,由于 n 个台阶可以 1, ... n 都可以调过来,状态转移通过 0, 1, ... n - 1 转移 dp[i] = dp[j] j < i import sys n = int(sys.stdin.readline().strip()) if n == 1: print...

Python3 数组动态规划

2022-02-18

3 594

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

动态规划, 每次走的步骤取决于前两个的状态; 状态转移方程: 当长度 < 2 时,直接返回 cost[0]; 当长度 >= 2 时,当前值取决于min(dp[i-1], dp[i-2]) + cost[i]; 代码如下: class Solution: def minCostCl...

Python3 动态规划

2022-02-17

6 1022

题解 | #信封嵌套问题#

dp 最大递增子序列问题。先对 letters 进行排序初始化 dp, dp[0] = 1 dp[i] = max(dp[j] + 1, dp[i]) j < i and letters[i][0] > letters[j][0] and letters[i][1] > le...

Python3 数组动态规划

2022-02-16

0 396

题解 | #连续子链表最大和#

利用动态规划的思想，最大子链表的和只与之前子链表+当前值和当前值有关，并用一个全局值记录整个过程中出现的最大值 # class ListNode: # def __init__(self, x): # self.val = x # self.next = ...

Python3 动态规划链表

2022-02-13

0 581

题解 | #礼物的最大价值#

二维 dp 问题,初始值 dp[0][0] = grid[0][0] 状态转移方程为： dp[i][j] = dp[i][j - 1] + grid[i][j] i == 0 & j > 0 dp[i][j] = dp[i - 1][j] + grid[i][j] i > 0 &...

Python3 动态规划

2022-02-11

2 528