fred-coder

分类

题解(149)

/ 注册

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

32篇文章 625人学习

全部文章（共28篇）

题解 | #Nim游戏# 来自专栏

动态规划 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param triangle int整型二维数组 # @return int整型 # class Solution: def minTrace(self , triangle: Li...

Python3 动态规划

2021-12-05

1 598

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

dp 解法，定义 dp 数组，转移方程为 dp[i] = max(dp[i], dp[j] + 1) j < i and arr[j] < arr[i] 因为每个数字算一位，初始值 dp = [1] * len(arr) 代码如下 # # 代码中的类名、方法名、参数名已经指定，请勿修改，...

Python3 动态规划

2021-11-23

2 690

题解 | #字母收集#

本题可利用动态规划进行求解，数据是 n * m 的矩阵，利用二维 dp，每次移动只能向右或向下，初始值 dp[0][0] = v00，第一行 dp[i][j] = dp[i - 1][j] + vij, 第一列 dp[i][j] = dp[i][j - 1] + vij, 当 i > 0 且...

Python3 动态规划

2021-11-13

0 401

题解 | #【模板】完全背包#

同上题类似,由于物品的数量有任意多个，则压缩 dp 后遍历时不采用逆序; 代码如下: n, v = map(int, input().strip().split()) dp_1 = [0 for _ in range(v + 1)] dp_2 = [float('-inf') for _ in ra...

Python3 动态规划

2021-11-12

2 444

题解 | #【模板】01背包#

01背包问题可用二维 dp，在遍历状态转移时，由于状态只与其中一个维度有关，可进行压缩;注意恰好装满，初始数组值为 -inf。代码如下: n, v = map(int, input().strip().split()) dp_1 = [0 for _ in range(v + 1)] dp_2 =...

Python3 动态规划

2021-11-12

1 520

题解 | #nico和niconiconi#

利用动态规划思路求解，构建 dp 数组，设置初始值，根据转移状态方程进行遍历，dp[i] 表示字符串 s[:i + 1] 内的最有价值值，则当 i >= 3 时, 若 s[i - 3: i + 1] == "nico" 时，有价值即 dp[i] = max(dp[i], dp[i - 3] +...

Python3 动态规划

2021-11-03

0 475

题解 | #不相邻取数#

根据题意，本题与"打家劫舍"的思路很相似，按照动态规划的思路，建立 dp 数组，赋初值，然后根据转移方程进行迭代；由于选取的数字是不相邻的数字，则 dp[i] 与 dp[i - 1] 和 dp[i - 2] + data[i] 有关，初始值 dp[0] = data[0], 动态规划数组每次进行状态...

Python3 动态规划数组

2021-11-01

0 501

题解 | #子数组最大连续和#

根据题意，求解连续数组的最大值，利用动态规划的思想，则可创建动态数组，然后赋值初始值，再根据状态转移方程进行遍历；本题中求解的是连续数组的最大值，设 dp[i] 表示数组 data[:i] 的最大值, 其值与 dp[i - 1] 和当前值 data[i] 有关, 若 dp[i - 1] + dat...

Python3 动态规划数组

2021-10-31

2 514