欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法学习之动态规划

程序员文章站 2024-03-17 17:14:34
...

动态规划

主要思想

若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题,例如斐波那契数列,如果运用递归的方式来求解会重复计算很多相同的子问题,利用动态规划的思想可以减少计算量。

动态规划法仅仅解决每个子问题一次,具有天然剪枝的功能,从而减少计算量,

一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。

动态规划模板步骤:

  • 确定动态规划状态
  • 写出状态转移方程(画出状态转移表)
  • 考虑初始化条件
  • 考虑输出状态
  • 考虑对时间,空间复杂度的优化(Bonus)

Leetcode300.最长上升子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
    	#先将特殊情况排除
        if not nums:
            return 0
        #设置dp的初始状态
        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)

leetcode674.最长连续递增序列

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

leetcode5.最长回文子串

        len1 = len(s)
        if len1 < 2:
            return s
        dp = [[False for i in range(len1)]for i in range(len1)]

        max_len = 1
        start = 0
        for j in range(1,len1):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
        
                if dp[i][j]:
                    current_len = j - i + 1
                    if current_len > max_len:
                        max_len = current_len
                        start = i
        return s[start:start+max_len]

leetcode516.最长回文子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        len1 = len(s)
        if len1 == 0:
            return 0
        if len1 == 1:
            return 1
        dp = [[0 for i in range(len1)]for i in range(len1)]
        for i in range(len1):
            dp[i][i] = 1
        max_len = 1
        for i in range(len1,-1,-1):
            for j in range(i+1,len1):
                if s[i] == s[j]:
                    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]

leetcode72.编辑距离

       def minDistance(self, word1, word2):
        #m,n 表示两个字符串的长度
        m=len(word1) 
        n=len(word2)
        #构建二维数组来存储子问题
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
        #考虑边界条件,第一行和第一列的条件
        for i in range(n+1):
            dp[0][i]=i  #对于第一行,每次操作都是前一次操作基础上增加一个单位的操作
        for j in range(m+1):
            dp[j][0]=j #对于第一列也一样,所以应该是1,2,3,4,5...
        for i in range(1,m+1):  #对其他情况进行填充
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]: #当最后一个字符相等的时候,就不会产生任何操作代价,所以与dp[i-1][j-1]一样
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 #分别对应删除,添加和替换操作
        return dp[-1][-1] #返回最终状态就是所求最小的编辑距离

leetcode198.打家劫舍

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

leetcode213.打家劫舍2

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        elif len(nums)<=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]))
相关标签: 算法 算法