动态规划思路解析

阿巩

坚决不咕咕咕！

动态规划绝对是面试前的算法必修课，它主要是用于解决求最值的问题。动态规划的核心即穷举，那么如何编写状态转移方程则成为动态规划算法思想的关键，这也正是它的难点所在。日拱一卒，迎难（男？）而上，让我们开始吧！

我们从三个力扣例题中体会下动态规划：

• 青蛙跳台阶
• 连续子数组的最大和
• 无重复字符的最长子串

青蛙跳台问题

首先来定义状态：dp[n]表示前n级台阶的跳法；然后来确定状态转移方程，假设已知n-1种跳法，当青蛙站在第n-1级台阶时只有一种跳法（即站在倒数第一级台阶），此时跳法为dp[n-1]*1；当青蛙在n-2级台阶时，由于之前已计算过在n-1级的跳法，所以不能跳到n-1级上，因此只有跳两级这一种跳法，那么dp[n-2]*1即为青蛙在n-2级时的跳法。

那么我们的状态转移方程，即n级台阶的跳法dp[n]=dp[n-1]+dp[n-2]。

1. 状态定义：dp[n]表示n级台阶的跳法
2. 状态转移方程：dp[n]=dp[n-1]+dp[n-2]
3. 初始状态：dp[0]=1, dp[1]=1
4. 返回值：dp[]数组的最后一个数

def numWays(n):
    if n == 0:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[-1] % 1000000007


n1 = 7
n2 = 2
print(numWays(n1), numWays(n2))
# 输出21 2

动态规划解法代码框架

# 初始化
dp[0][0][...] = base
# 状态转移
for 状态1 in 状态1的全部取值：
    for 状态2 in 状态2的全部取值：
        ...
        dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)

连续子数组的最大和

题目满足动态规划的两点标准，穷举和求最值，动态规划也正是本题的最优解法。我们还按四步走的方法来分析下：

1. 状态定义：dp[i]表示以nums[i]结尾的连续子数组最大和
2. 状态转移方程：若dp[i-1]<=0：dp[i] = nums[i]；若dp[i-1]>0：dp[i]=dp[i-1]+nums[i]
3. 初始状态：dp[0] = nums[0]
4. 返回值：返回dp列表中的最大值，即max(dp)

def maxSubArray(nums):
    if not nums:
        return
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        if dp[i - 1] < 0:
            dp[i] = nums[i]
        else:
            dp[i] = nums[i] + dp[i - 1]
    return max(dp)
    
    
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))
# 输出6

空间复杂度优化：由于dp[i]只与dp[i-1]和nums[i]有关，因此可以将nums作为dp列表，直接在nums上修改即可。不需要引入dp列表，空间复杂度降为O(1)。

我们还可以使用max(nums[i-1], 0)表达式来简化if else判断，优化代码如下：

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

无重复字符的最长子串

这个题的出场频率在今年面试中相当高，下图是CodeTop统计的在大厂面试中出现次数：

1. 状态定义：dp[j]表示以s[j]结尾的 “最长不重复子字符串” 的长度。
2. 状态转移方程：固定右边界j，设字符s[j]左边距离最近的相同字符为s[i]，即s[i] = s[j]。 当dp[j-1] < j - i 说明s[i]在dp[j-1]区间外，则dp[j] = dp[j-1] + 1； 当dp[j-1] >= j - i 说明s[i]在dp[j-1]区间内，则dp[j]的左边界由s[i]确定，即dp[j] = j - i。
3. 返回值：最长不重复子字符串的长度max(dp)

空间复杂度优化:

由于返回值取dp列表最大值，借助tmp存储dp[j]，变量res每轮刷新最大值即可。节省dp列表O(N)的额外空间开销。

这里引入哈希表来统计各字符最后一次出现的索引位置，即遍历到s[j]时，通过dic[s[j]]获取最近相同字符的索引i。

def lengthOfLongestSubstring(s):
    dic = {}
    res = tmp = 0
    for j in range(len(s)):
        i = dic.get(s[j], -1)  # 获取索引 i
        dic[s[j]] = j  # 更新哈希表
        tmp = tmp + 1 if tmp < j - i else j - i  # dp[j - 1] -> dp[j]
        res = max(res, tmp)  # max(dp[j - 1], dp[j])
    return res


s = "abcabcbb"
print(lengthOfLongestSubstring(s))
# 输出3

END