爱读书的菠萝蜜很想去杭州

分类

/ 注册

全部文章（共62篇）

题解 | 【模板】01背包

import sys from math import inf n,v = map(int,input().split()) a = [list(map(int,input().split())) for _ in range(n)] # dp[i][j]定义为装前i个物品在容量为j的情况下的最大价...

2025-07-17

0 11

题解 | 求路径 ii

# # # @param obstacleGrid int整型二维数组 # @return int整型 # class Solution: def uniquePathsWithObstacles(self , obstacleGrid ): # write code h...

2025-07-11

0 17

题解 | 计算字符串的编辑距离

from math import inf s = input() t = input() # dp[i][j]为s的前i个字符和t的前j个字符的编辑距离 # dp[0]=list(range(m+1)),dp[][0]=list(range(n+1)) # 那么关键递推式是什么呢？ # if s[i...

2025-07-11

0 24

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

n,m = map(int,input().split()) s1 = input() s2 = input() # 空间优化方案(滚动数组) curr = [0]*(m+1) for i in range(1,n+1): prev = curr curr = [0]*(m+1) ...

2025-07-10

0 18

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

n,m = map(int,input().split()) s1 = input() s2 = input() # **dp[i][j]定义为s1前i个字符和s2前j个字符的最长公共子序列 # 在已知dp[x][y](x<i,y<i)的前提下如何得到dp[i][j]？ # if s1[...

2025-07-10

0 18

题解 | 三角形最小路径和

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

2025-07-10

0 22

题解 | 打家劫舍(二)

import sys n = int(input()) a = list(map(int,input().split())) # 环形，所以拆成两个数组a[0:n-1],a[1:n] # dp[i]定义为偷到第i个房子的偷盗最大金额 if n == 1: print(a[0]) sy...

2025-07-10

0 17

题解 | 连续子数组最大和(ACM版本)

from math import inf n = int(input()) a = list(map(int,input().split())) # 注意是连续的 # dp[i]定义为以索引i的数字结尾的连续子数组的最大和 dp = [-inf]*n dp[0] = a[0] for i in ra...

2025-07-10

0 19

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

n = int(input()) arr = list(map(int,input().split())) # dp[i]表示以索引i的数字结尾的递增子串的最大长度 dp = [1]*n for i in range(1,n): for j in range(i): if a...

2025-07-10

0 17

题解 | 斐波那契数列

import sys n = int(input()) if n == 1 or n == 2: print(1) sys.exit() # 动态规划模板法 dp = [0]*(n+1) # 索引0闲置 dp[1],dp[2] = 1,1 for i in range(3,n+1):...

2025-07-09

0 14