算法篇——动态规划网站首页 技术交流

算法篇——动态规划

橙意满满的西瓜大侠 2025-05-13 12:01:03

简介算法篇——动态规划

核心思想：

将问题分解为重叠的子问题，并储存子问题的解（使用字典、数组或哈希表），避免重复计算，从而提高效率。

题目特点：重叠子问题（特殊地，是最优子结构）

比如：斐波那契数列问题中，递归求F(5)，需要多次计算F(3)；

最短路径问题中，若从A到C的最优路径包含B，则A到B和B到C也必然是最优的。

两种实现方式：

自顶向下（递归+储存记忆，将大问题逐步分解，子问题的解储存在字典里）：

class Solution(object):
    # 把momory作为类属性
    memory = {}

    def fib(self, n):
        # 如果已经在记忆里储存，则直接返回，不用再重复计算
        if n in self.memory: 
            return self.memory[n]

        if n<=1:
            return n

        self.memory[n] = self.fib(n-1)+self.fib(n-2)
        return self.memory[n]

自底向上（迭代+储存记忆，先解决小问题再解决大问题，小问题的解储存在数组里）：

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0,1] # 动态规划数组，初始值相当于递归里遇到终止条件能直接返回的值

        for i in range(2,n+1):
            dp.append(dp[i-1]+dp[i-2])
        
        return dp[n]

解题步骤：

1、定义状态（dp[i]表示什么）

2、写状态转移方程（由局部最优一直推到全局最优，所以从初始截断到当前位置来考虑即可，后面的先不管）

3、确定初始状态（起码两个）

3、用递归or迭代解题

比如：“打家劫舍”求数组中不相邻元素组合，使值的和最大

（1）定义状态：设dp[i]表示从第0到第i个中元素组合的最优解；

（2）状态转移方程：

则可以分类讨论：目前最优解要不要加上dp[i]这个元素，

即是取dp[i-1]还是dp[i-2]+nums[i]，

比较两者取较大值就行。

得方程，dp[i] = max（dp[i-1]，dp[i-2]+nums[i]）

（3）初始条件：dp[0]=1，dp[1]=max（nums[0]，nums[1]）

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n==1:
            return nums[0]

        dp = [nums[0],max(nums[0],nums[1])] #注意基础条件里，nums[1]不一定有，需要分类讨论

        for i in range(2,n):
            dp.append(max(dp[i-1],dp[i-2]+nums[i]))
        
        return dp[n-1]

删除并获得点数

class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # 转换思维：统计每个数字的总点数，生成一个数组sums[x] = x*count(x)
        # 接着，类似于打家劫舍问题，取不相邻的元素，使元素的和最大
        # 设dp[i]为遍历到i的最优解，dp[i] = max(dp[i-1],dp[i-2]+sums[i])

        # 生成sums数组（先找到nums[i]的最大值，用它作为sums数组的最大边界）
        max_num = max(nums)
        sums = [0] * (max_num+1) #初始化
        for num in nums:
            sums[num] += num

        # 动态规划求解
        if len(sums) == 1:
            return 0
        dp = [0,sums[1]]
        #dp = [sums[0],max(sums[0],sums[1])]

        for i in range(2,len(sums)):
            dp.append(max(dp[i-1],dp[i-2]+sums[i]))

        return dp[len(sums)-1]

优化技巧：

1、滚动变量替代dp数组

class Solution(object):
    def rob(self, nums):
        n = len(nums)
        if n==1:
            return nums[0]
        # 滚动变量优化空间，不需要整个dp数组
        pre, cur = nums[0],max(nums[0],nums[1]) #dp = [nums[0],max(nums[0],nums[1])]
        for i in range(2,n):
            pre, cur = cur, max(cur, pre+nums[i])
            #dp.append(max(dp[i-1],dp[i-2]+nums[i]))
        return cur

可以理解为先计算temp = max(cur, pre + nums[i])，然后让pre=cur，再让cur=temp。

最长回文子串：

（1）定义状态：dp[i][j]表示字符串从第i个字符到第j个字符是否为回文字符串。

（2）状态转移方程：

往子问题方向拆分——如果dp[i][j]是回文子串，那么两端的字符必定相等，而且中间的字符串（如果有）也应该是回文子串。即

dp[i][j] = （s[i]==s[j]）&&（（j==i+1）or dp[i+1][j-1]）

（3）初始条件：

只有一个字符，dp[i][i]=True

则，可以总结出：dp[i][i]=True

dp[i][j] = （s[i]==s[j]）&& （（j==i+1）or dp[i+1][j-1]）

迭代法的状态转移：判断首尾相等后，每个位置的状态和它的左下角的状态有关

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        if n<=1:
            return s
        
        # 初始化动态规划表
        dp = [[False]*n for _ in range(n)]

        # 初始条件：所有长度为1的子串都是回文
        for i in range(n):
            dp[i][i] = True
        max_len = 1
        start = 0 #追踪最长回文子串的起始位置

       # dp[i][j] = （s[i]==s[j]）&& （（j==i+1）|| dp[i+1][j-1] ）
        for j in range(1,n): #右指针，子区间的右边界，从1到n-1
            for i in range(0,j): #左指针，子区间的左边界，从0到j-1
                if s[i]==s[j]: #如果左右边界相等
                    if (j==i+1) or (dp[i+1][j-1]): #如果没有中间部分或者中间部分也是回文子串
                        dp[i][j] = True #标记

                        length = j-i+1
                        if length>max_len: #看需不需要更新
                            max_len=length
                            start=i 

        return s[start:start+max_len]

[False] * n 借助列表乘法操作，将包含单个 False 的列表重复 n 次，从而生成一个长度为 n 且所有元素都为 False 的一维列表。

_ 是 Python 里的一个惯用变量名，通常用于表示一个临时的、不会被使用的变量。

s[start:start+max_len] 是 Python 中用于字符串切片操作（左闭右开）的表达式。它的作用是从字符串 s 中提取一个子字符串，该子字符串从索引 start 开始，到索引 start + max_len - 1 结束。