- Leetcode303 区域和检索
- Leetcode392 判断子序列
- Leetcode746 最小花费爬楼梯
- Leetcode1025 除数博弈
特别鸣谢廖老师教我动态规划,以前对动态规划没有一个很理性的认识。可能这道题会dp都是瞎蒙出来的,换个题 甚至换个条件就无从下手了,现在对简单的DP题至少是头脑比较清晰了,谢谢廖老师 谢谢廖老师!
以DP解法为主
下面题目顺序按上面4个来做 ,针对每道题当然有比DP更好的解法,在这里我们主要只讨论DP方法
题目描述
class NumArray: def __init__(self, nums: List[int]): self.dp = [0] * len(nums) if nums: self.dp[0] = nums[0] for i in range(1,len(nums)): self.dp[i] = self.dp[i-1] + nums[i] def sumRange(self, i: int, j: int) -> int: if not self: return null return self.dp[j]-self.dp[i-1] if i>0 else self.dp[j] # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # param_1 = obj.sumRange(i,j)
Note
- 简单的DP题,状态转移方程很好列
- 但其实做题的时候遇到了
- self.dp来把dp作为全局变量(不知道描述的是不是准确)其实不是一开始就想到的
- nums非空的边界条件未考虑,空的时候返回null题目未表述清楚 这是题目出得不够好。
题目描述
# class Solution: # def isSubsequence(self, s: str, t: str) -> bool: # m = len(s) # n = len(t) # if not m: # return True # if not n: # return False # if m==1: # return s in t # dp= [[False]*n for i in range(m)] # for j in range(n): # dp[0][j] = True # for i in range(1,m): # for j in range(1,n): # if(s[i] == t[j]): # dp[i][j] = dp[i-1][j-1] # else: # dp[i][j] = dp[i][j-1] # return dp[m-1][n-1] class Solution: def isSubsequence(self, s: str, t: str) -> bool: m,n = len(s),len(t) if not m: return True if not n: return False for item in s: temp = t.find(item) if temp == -1: return False t = t[temp+1:] return True
Note
- 这道题总体有点像LCS问题,但是用二维数组做DP会超时,降到一维应该没问题。具体降法实现有空再写。。(咕咕咕?)
- 先讲下二维数组DP的方法
- 首先dp[i][j]表示字符串s、t的前i个、前j个字符组成的串(记住我们要判断s是否属于t的子序列),不妨记为si,tj,于是当si为tj子序列时dp[i][j]=True否则为False
- 那么考虑两种情况,
- 当s[i]=t[j]时,s中第i个和t中第j个字符显然不对si、tj的从属关系做贡献了,也就是说实际上此时s[i]、t[j]可以直接抹去不看, 即dp[i][j]=dp[i-1][j-1]
- 当s[i]!=t[j]时,t中第j个字符也无法对si是否属于t的子序列做贡献了,于是有dp[i][j]=dp[i][j-1]
- 最终return dp[m-1][n-1]
- 上面过程可能也有出错的地方OvO
- 方法二是切片法,也是我最终ac的代码,其义自明。
题目描述
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = cost n = len(cost) if(n>2): for i in range(2,n): dp[i] = min(dp[i-1],dp[i-2])+cost[i] return min(dp[n-2],dp[n-1]) else: return min(dp[0],dp[1])
Note
- 简单的DP题
题目描述
class Solution: def divisorGame(self, N: int) -> bool: dp = [False] * (N+1) if N<=1: return False dp[2] = True for i in range(3, N+1): for j in range(1,i//2): if i%j == 0 and dp[i-j]==False: dp[i] = True break return dp[N]
Note
- 比较tricks的解法是类似之前的Nim游戏,找规律发现偶数必胜否则必输,所以一行return N%2==0即可
- 但我们还是在学习DP解法
- dp[i]表示当前数字为i时,Alice获胜的情况,True表示胜利否则失败,初始化为False
- 不难知道当Alice面对1则输面对2则胜,且根据游戏规则有dp[i]、dp[i-j]有且只有一个为False,转移方程大概是形如dp[i]+dp[i-j]=1这样
- 和普通dp不同的只是j需要满足i%j===0而已 题目可解
忘了写了 python二维数组初始化方法之一
dp = [[0]*n for i in range(m)]