Leetcode DP简单题4道

• 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题，状态转移方程很好列
• 但其实做题的时候遇到了

1. self.dp来把dp作为全局变量（不知道描述的是不是准确）其实不是一开始就想到的
2. 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的方法
  1. 首先dp[i][j]表示字符串s、t的前i个、前j个字符组成的串（记住我们要判断s是否属于t的子序列），不妨记为si，tj，于是当si为tj子序列时dp[i][j]=True否则为False
  2. 那么考虑两种情况，
  3. 当s[i]=t[j]时，s中第i个和t中第j个字符显然不对si、tj的从属关系做贡献了，也就是说实际上此时s[i]、t[j]可以直接抹去不看， 即dp[i][j]=dp[i-1][j-1]
  4. 当s[i]!=t[j]时，t中第j个字符也无法对si是否属于t的子序列做贡献了，于是有dp[i][j]=dp[i][j-1]
  5. 最终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而已 题目可解