动态规划

pykt 收录于刷题笔记

2022-11-06 约 1612 字预计阅读 4 分钟

基本介绍

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。适用动态规划的问题必须满足最优化原理和无后效性：

最优化原理

一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

在求解动态规划的问题的时候，常会涉及到状态转移方程：

状态转移方程

状态转移方程，是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第$K$阶段的状态$S_k$以及决策$u_k(S_k)$，则第$K+1$阶段的状态$S_{k+1}$也就完全确定。

示例：简单动态规划题目的状态转移方程

题目链接：LeetCode爬楼梯

题目：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

解答：设$dp[i]$为当第$i$个阶梯的时候有$dp[i]$中方法，可知$dp[0]=1, dp[1]=1$，则状态转移方程如下：

$$dp[i] = dp[i-1] + dp[i-2], 1<= i <=n $$

得出状态转移方程之后，我们可以轻松的得到对应的代码，以下以Python代码给出解答：

1
2
3
4
5
6
7
8


class Solution:
    def climbStairs(self, n: int) -> int:
        x_1, x_2, tmp = 1, 1, 1  # 滑动
        for i in range(2, n+1):
            tmp = x_1 + x_2
            x_1 = x_2
            x_2 = tmp
        return tmp

经典应用场景

最长不下降子序列

最长不下降子序列（Longest Increasing Sequence, LIS）是这样一个问题：

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降的。

示例：最长递增子序列

LeetCode题目链接

题目：给你一个整数数组nums，找到其中最长严格递增子序列的长度。

解答：设$dp[i]$是以nums[i]为结尾的最长递增子序列长度，可以获得如下的状态转移方程： $$dp[i] = \max{dp[j] + 1, 1} $$，其中$num[i] > num[j], 0 <= j <= i - 1$，且知初始值dp[0] = 1。于是，可以写出如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1]
        for i in range(1, len(nums)):
            tmp = 1
            for j in range(i):
                if nums[i] > nums[j] and dp[j] + 1 > tmp:
                    tmp = dp[j] + 1
            dp.append(tmp)
        # 遍历拿到最大的
        return max(dp)

最长回文子串

最长回文子串的问题描述∶

给出一个字符串S，求S的最长回文子串的长度。

以下是示例：

字符串"PATZJUZTACCBCC"的最长回文子串为"ATZJUZTA"，长度为9。

示例：统计不同回文子序列

LeetCode题目链接

LeetCode参考题解链接

如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。

题目：给定一个字符串s，返回s中不同的非空回文子序列个数。通过从s中删除0个或多个字符来获得子序列。

解答：设dp[i][j]表示字符串从i到j的回文序列个数，状态转移方程如下： $${\tiny dp[i][j]=\left\{\begin{aligned} & 1, & i==j \\& 2dp[i+1][j-1]+2, & s[i]==s[j],i \neq j,无重复字符 \\& 2dp[i+1][j-1]+1, & s[i]==s[j],i \neq j,一个重复字符 \\& 2dp[i+1][j-1] - dp[left+1][right-1], & s[i]==s[j],i \neq j,两个及以上的重复字符 \\& dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1], & s[i] \neq s[j]\end{aligned}\right.}$$

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        mod = 1000000007
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n): dp[i][i] = 1

        for cur_len in range(2, n+1):  # 从长度为2的子串开始计算
            # 挨个计算长度为len的子串的回文子序列个数
            for i in range(0, n-cur_len+1):
                j = i+ cur_len -1
                # 情况(1) 相等
                if s[i] == s[j]:
                    l, r = i+1, j-1
                    while l <= r and s[l] != s[i]: l += 1
                    while l <= r and s[r] != s[j]: r -= 1
                    if l > r:  # 情况① 没有重复字符
                        dp[i][j] = 2 * dp[i+1][j-1] + 2
                    elif l == r:   # 情况② 出现一个重复字符
                        dp[i][j] = 2 * dp[i+1][j-1] + 1
                    else:  # 情况③ 有两个及两个以上
                        dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]
                else:  # 情况(2) 不相等
                    dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]
                dp[i][j] = dp[i][j] % mod  # Python直接取模也没有问题
        return dp[0][n-1]

背包问题

背包问题是一类经典的动态规划问题，可以分为01背包问题以及完全背包问题。

凑零钱问题

参考文献

代码随想录

目录