2.算法-动态规划

LIS问题

连续子数组最大和 

def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i] = max(nums[i-1]+nums[i],nums[i])
        return max(nums)

最长连续递增子序列长度

def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [1] * len(nums)
        for i in range(1,len(nums)):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
            else :
                dp[i] = 1
        return max(dp)

最长递增子序列长度

解法一：DP
def lengthOfLIS(self, nums: List[int]) -> int:
        if(not nums):
            return 0
        dp = [1]*len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)
[进阶] 解法二：贪心+二分

思路：数组d[len]表示长度为len的的子序列末尾最大值,遍历数组时用二分查找得到插入d的位置
举例：[0, 8, 4, 12, 2]

第一步插入 0，d = [0]
第二步插入 8，d = [0, 8]
第三步插入 4，d = [0, 4]
第四步插入 12，d = [0, 4, 12]
第五步插入 2，d = [0, 2, 12]
最终得到最大递增子序列长度为 3

[再进阶] 输出该序列

思路：要输出序列，就要确定序列的最大值，然后从后向前遍历数组
解法一知道以每个元素结尾的最长子序列长度
解法二知道固定长度子序列结尾的最小值
结合这两个信息就可以还原最长子序列

def LIS(arr):
        if not arr: return None
        n = len(arr)
        d = [arr[0]] 
        dp = [1] * n # 记录以元素 arr[i] 结尾的最长递增子序列的长度
        length = 1
        for i in range(1,n): # 从1开始遍历
            if arr[i] > d[-1]:
                d.append(arr[i]) 
                length += 1
                dp[i] = length
            else:
                # 使用bisect库
                index = bisect.bisect(d,arr[i])
                dp[i] = index + 1 # 找到的是下标，长度需要再加1
                d[index] = arr[i] # 插入到对应位置
                # 手动实现二分
                l, r = 0, len(d)-1
                loc = -1
                while (l <= r):
                    mid = (l+r)//2
                    if (arr[i] <= d[mid]):
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                dp[i] = loc + 1
                d[loc] = arr[i] 

        ans = []
        max_val = d[-1] 
        count = len(d)
        idx  = arr.index(max_val)
        
        for i in range(idx,-1,-1):
            if not ans or (arr[i] < ans[-1] and dp[i] == count):
                ans.append(arr[i])
                count -= 1
        return ans[::-1]

回文问题

最长回文子串(长度)

def longestPalindrome(s) ：
        N = len(s)
        if N == 1: 
            return s
        dp = [[False for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dp[i][i] = True
        max_len,start = 1,0
        for j in range(1,N):  #因为后面外层j-1所以j要从1开始
            for i in range(j): # i一定是小于j的，所以是循环到j
                if(s[i] == s[j]):
                    if(j-i<3): #为什么这里是3  i+1 和 j-1 的距离小于1 j-1-(i+1)<1其实也就是 i+1和j-1相等，是一个字符的时候，肯定满足回文
                        dp[i][j]=True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if(dp[i][j]):
                    l = j - i + 1
                    if(l > max_len):
                        max_len = l 
                        start = i
        return s[start:start+max_len]

这道题要注意一个比较重要的点，至少对我来说比较重要，就是在写二重循环的时候，为什么是先遍历j 然后再遍历i , 我们看下我们的思路中的这个公式 dp[i][j] = dp[i+1][j-1] 要有了后面的值才能赋值给前面，从这个二维矩阵就可以看出，列是外层循环，i是内层循环，这样就不会出错了

最长回文子序列长度

def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0]*n for _ in range(n)]  #定义动态规划状态转移矩阵
        for i in range(n):  #   初始化对角线，单个字符子序列就是1
            dp[i][i]=1
        for i in range(n-1,-1,-1):  #从右下角开始往上遍历 注意这里是n-1不是n
            for j in range(i+1,n):
                if s[i]==s[j]:   #当两个字符相等时，直接子字符串加2
                    dp[i][j]= dp[i+1][j-1]+2  
                else:           #不相等时，取某边最长的字符
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])
        return dp[0][-1]   #返回右上角位置的状态就是最长

221 最大正方形 字节

思路已经有了，但是最后有的case没有通过，还不知道为什么

def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        r,c = len(matrix),len(matrix[0])
        if r == 0 or c == 0 : return 0
        dp = [[int(matrix[i][j]) for j in range(c)] for i in range(r)]
        fr,fc = dp[0], [dp[i][0] for i in range(r)]
        l = max(max(fr),max(fc))
        for i in range(1,r):
            for j in range(1,c):         
                tmp = dp[i-1][j-1]
                if(matrix[i][j]=='1' and tmp>0):
                    flag =  True
                    index = 0 
                    while index < tmp:
                        if matrix[i-index-1][j] == '0' or matrix[i][j-index-1] == '0':
                            flag = False
                            break
                        index += 1
                    if flag:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = dp[i-1][j-1]
                l = max(l,dp[i][j])
        return l*l

和正确答案对比一下, 如何巧妙地把边界条件包含在循环中而不是单独判断

def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        
        maxSide = 0
        rows, columns = len(matrix), len(matrix[0])
        dp = [[0] * columns for _ in range(rows)]
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    maxSide = max(maxSide, dp[i][j])
        
        maxSquare = maxSide * maxSide
        return maxSquare

1024. 视频拼接

这道题其实DP的思路不是很好想, 感觉贪心更好想
用dp[i]表示覆盖[0,i)需要的最小空间数

def videoStitching(self, clips: List[List[int]], T: int) -> int:
        l = len(clips)
        dp = [0] + [l+1]*T #0一定是0了，其他初始化一个不可能的大数len(clips)+1
        for i in range(1,T+1):
            for aj,bj in clips:
                if aj < i <= bj: #[0,i)的后面部分可以被覆盖
                    #如果用这个部分覆盖，数目为dp[aj]+1 不用就是dp[i] 取最小值
                    dp[i] = min(dp[i],dp[aj]+1)
        return -1 if dp[T]==l+1 else dp[T]

139. 单词拆分

继续动态规划

1. 72. 编辑距离 

def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        #这里注意初始化的二维数组的时候，哪个在里面，哪个在外面
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)] 
        for i in range(m+1):
            dp[i][0] = i 
        for j in range(n+1):
            dp[0][j] = j
        for i in range(1,m+1):
            for j in range(1,n+1):
                if(word1[i-1]==word2[j-1]):
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
        return dp[-1][-1]

2.198. 打家劫舍 

def rob(self, nums: List[int]) -> int:
        N = len(nums)
        if not nums:
            return 0
       
        if N == 1 : return nums[0]
        if N == 2 : return max(nums[0],nums[1])

        dp = list(range(N))
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        return dp[-1]

3.213. 打家劫舍 II

怎么能想到把这问题拆分成 只抢第一家 和 只抢最后一家 两个子问题？？？

def rob(self, nums: List[int]) -> int:
        N = len(nums)
        if not nums : return 0 
        if N <= 2 : return max(nums)

        def helper(nums):
            if len(nums) <= 2 : return max(nums)
            dp = [0] * len(nums)
            dp[0] = nums[0]
            dp[1] = max(nums[0],nums[1])
            for i in range(2,len(nums)):
                dp[i]=max(dp[i-1],dp[i-2]+nums[i])
            return dp[-1]
            
        return max(helper(nums[1:]),helper(nums[:-1]))

2 72. 编辑距离

我看到“方法一”三个字的时候，惊喜地以为还有方法二。。没有，这次真没有。动态规划是个好东西，但难就难在如何定义DP数组里值的含义。听我来给你捋一捋。

啥叫编辑距离？我们说word1和word2的编辑距离为X，意味着word1经过X步，变成了word2，咋变的你不用管，反正知道就需要X步，并且这是个最少的步数。

我们有word1和word2，我们定义dp[i][j]的含义为：word1的前i个字符和word2的前j个字符的编辑距离。意思就是word1的前i个字符，变成word2的前j个字符，最少需要这么多步。

例如word1 = "horse", word2 = "ros"，那么dp[3][2]=X就表示"hor"和“ro”的编辑距离，即把"hor"变成“ro”最少需要X步。

如果下标为零则表示空串，比如：dp[0][2]就表示空串""和“ro”的编辑距离

定理一：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。比如空串“”和“ro”的编辑距离是2（做两次“插入”操作）。再比如"hor"和空串“”的编辑距离是3（做三次“删除”操作）。

定理二：当i>0,j>0时（即两个串都不空时）dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))。

啥意思呢？举个例子，word1 = "abcde", word2 = "fgh",我们现在算这俩字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：

知道"abcd"变成"fgh"多少步（假设X步），那么从"abcde"到"fgh"就是"abcde"->"abcd"->"fgh"。（一次删除，加X步，总共X+1步）
知道"abcde"变成“fg”多少步（假设Y步），那么从"abcde"到"fgh"就是"abcde"->"fg"->"fgh"。（先Y步，再一次添加，加X步，总共Y+1步）
知道"abcd"变成“fg”多少步（假设Z步），那么从"abcde"到"fgh"就是"abcde"->"fge"->"fgh"。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）
以上三种方式算出来选最少的，就是答案。所以我们再看看定理二：

dp[i][j]=min(dp[i-1][j]+1,dp[i][j+1]+1,dp[i][j]+int(word1[i]!=word2[j]))
dp[i-1][j]：#情况一
dp[i][j-1]+1：#情况二
dp[i-1][j-1]+int(word1[i]!=word2[j])：#情况三

有了定理二的递推公式，你就建立一个二维数组，考虑好空串的情况，总会写出来

进阶

先把二维数组的方法做出来，要还没做出来呢，先别往下看。

由定理二可知，dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个量有关，即二维数组中，当前元素的左边，上边，左上角三个元素。

那我们不用这么大的二维数组存啊！我们就用一维数组，表示原来二维数组中的一行，然后我们就反复覆盖里面的值。dp[i-1][j]就是我当前左边的元素，dp[i][j-1]是没覆盖前我这里的值，dp[i-1][j-1]好像找不见了？那我们就单独用一个变量存着它，我们把它叫lu（left up），则代码为：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m=len(word1)
        n=len(word2)
        dp=list(range(n+1))
        for i in range(m):
            lu=dp[0]
            dp[0]=i+1
            for j in range(n):
                dp[j+1],lu=min(dp[j]+1,dp[j+1]+1,lu+int(word1[i]!=word2[j])),dp[j+1]
        return dp[-1]

5. 16. 最接近的三数之和

有了之前3数之和的经验，这个还是解答起来比较简单的

def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        distance = pow(10,4)
        res = 0
        for i in range(len(nums)):
            low, high = i + 1, len(nums)-1
            while(low < high):
                sum_value = nums[i] + nums[low] + nums[high]
                if abs(sum_value-target) < distance:
                    distance = abs(sum_value-target)
                    res = sum_value
                if (sum_value > target):
                    high -= 1
                elif (sum_value == target):
                    return target
                else:
                    low += 1
        return res

6. 454. 四数相加 II

这题目用我大python有点牛逼了。。。也太简洁明快了

def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        record = collections.Counter(a + b for a in A for b in B)
        return sum(record.get(- c - d, 0) for c in C for d in D)

4. 剑指 Offer 60. n个骰子的点数

这确定是个简单题目么。。。？感觉还是有点复杂的，

从题解来看，刷到了第一个动态规划的题目。那么我们来理一下DP问题的思路吧
  • 首先要确定如何表示状态 用dp[n][j]表示投掷完 n 枚骰子后，点数 j 的出现次数
  • 然后找出状态转移方程，dp[n][j] = dp[n-1][j-1] + ... dp[n-1][j-6]
  • 最后确定边界条件 投掷完 1 枚骰子后,点数从1到6各出现一次 dp[1][i]=1
def twoSum(self, n: int) -> List[float]:
        dp = [ [0 for _ in range(6*n+1)] for _ in range(n+1)] #如何初始化一个n行6n列的二维数组
        for i in range(1,7):
            dp[1][i] = 1
        for i in range(2,n+1):
            for j in range(i,i*6+1):
                for k in range(1,7):
                    if(j>k):
                        dp[i][j]+=dp[i-1][j-k]
        res = []
        for i in range(n,6*n+1):
            res.append(dp[n][i]*1.0/6**n)
        return res

反复品了一下，好像又没有那么难，重点在于思路、套路

5. 剑指 Offer 49. 丑数

1003am-1023am
有事耽误了几天，看了下答案，好吧，表示自己真得想不出来 mark
三指针动态规划问题

def nthUglyNumber(self, n: int) -> int:
        dp, a, b, c = [1] * n, 0, 0, 0
        for i in range(1, n):
            n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
            dp[i] = min(n2, n3, n5)
            if dp[i] == n2: a += 1
            if dp[i] == n3: b += 1
            if dp[i] == n5: c += 1
        return dp[-1]
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,271评论 5赞 466
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,725评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,252评论 0赞 328
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,634评论 1赞 270
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,549评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 47,985评论 1赞 275
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,471评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,128评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,257评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,233评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,235评论 1赞 328
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,940评论 3赞 316
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,528评论 3赞 302
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,623评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,858评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,245评论 2赞 344
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,790评论 2赞 339