Leetcode DP简单题4道

/ 1评 / 0

特别鸣谢廖老师教我动态规划,以前对动态规划没有一个很理性的认识。可能这道题会dp都是瞎蒙出来的,换个题 甚至换个条件就无从下手了,现在对简单的DP题至少是头脑比较清晰了,谢谢廖老师 谢谢廖老师!

以DP解法为主

下面题目顺序按上面4个来做 ,针对每道题当然有比DP更好的解法,在这里我们主要只讨论DP方法

题目描述

file

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

  1. self.dp来把dp作为全局变量(不知道描述的是不是准确)其实不是一开始就想到的
  2. nums非空的边界条件未考虑,空的时候返回null题目未表述清楚 这是题目出得不够好。

题目描述

file

# 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

题目描述

file

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

题目描述

file

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

一条回应:“Leetcode DP简单题4道”

  1. 折纸说道:

    忘了写了 python二维数组初始化方法之一
    dp = [[0]*n for i in range(m)]

发表评论

电子邮件地址不会被公开。