14.2 单序列问题

单序列问题的输入通常是一个序列, 如数组或字符串.

动态规划解决单序列问题关键的一步是在序列中增加一个元素, 根据题目的特点找出元素对应的最优解(或解的个数)和前面若干元素的最优解(或解数目)的关系, 并得出状态转移方程.

在状态转移方程到代码实现的过程中, 要时刻注意重复计算的问题和缓存优化的问题.

14.2.1 问题89: 房屋偷盗

LCR 089. 打家劫舍

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

14.2.2 分析&题解

小偷进入一次只能进一幢房屋, 到所有房屋中需要多个步骤, 每一步有两个选择, 因为需要最优解, 所以使用动态规划.

状态转移方程

假设房屋为nums[0, n-1], 在第i幢房屋时能获得的最大金额为$f(i)$, 此时有两个选择:

• 进入i, 则表示i-1没有进入过, $f(i)=f(i-2)+nums[i]$
• 不进入i, 则表示i-1进入过了, $f(i)=f(i-1)$

那么$f(i)$的最优解为$f(i)=max(f(i-2)+nums[i], f(i-1))$

注意隐含的状态:

• i=1时, 只有两幢房屋, 最优解 $f(1) = max(nums[0], nums[1])$
• i=0时, $f(0) = nums[0]$

递归+缓存

将状态转移方程转换成递归代码, 并使用缓存避免重复计算

func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    // 缓存
    dp := make([]int, n)
    for i := range dp {
        dp[i] = -1
    }

    // 子问题
    helper(nums, dp, n-1)   

    // 最优解
    return dp[n-1]
}

// 状态转移方程
func helper(nums, dp []int, idx int) {
    // 最小问题
    if idx == 0 {
        dp[idx] = nums[0]
    } else if idx == 1 {
        dp[idx] = max(nums[0], nums[1])
    } else if dp[idx] == -1 { // 未计算过
        // 子问题
        helper(nums, dp, idx-2)
        helper(nums, dp, idx-1)

        // 当前问题最优解
        dp[idx] = max(dp[idx-2]+nums[idx], dp[idx-1])
    }
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

迭代 SC: O(n)

func rob(nums []int) int {
    n := len(nums)
    // 边界
    if n == 0 {
        return 0
    }
    
    // 缓存
    dp := make([]int, n)
    // 最小问题
    if n >= 1 {
        dp[0] = nums[0]
    }
    if n >= 2 {
        dp[1] = max(nums[0], nums[1])
    }

    for i := 2; i < n; i++{
        dp[i] = max(dp[i-2]+nums[i], dp[i-1])
    }

    return dp[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

迭代 SC: O(1)

根据状态转移方程 $f(i)=max(f(i-2)+nums[i], f(i-1))$, 当前最优解只和前两个的子问题最右解有关, 那么缓存就可以将长度优化为2.

func rob(nums []int) int {
    n := len(nums)
    // 边界
    if n == 0 {
        return 0
    }

    // 缓存
    dp := make([]int, 2)
    // 最小子问题
    if n >= 1 {
        dp[0] = nums[0]
    }
    if n >= 2 {
        dp[1] = max(nums[0], nums[1])
    }

    for i := 2; i < n; i++ {
        a := (i-2) % 2
        b := (i-1) % 2
        dp[i%2] = max(dp[a]+nums[i], dp[b])
    }

    return dp[(n-1)%2]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

两个状态转移方程

// TODO: 2023-09-15

14.2.2 问题90: 环形房屋偷盗

LCR 090. 打家劫舍 II

一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

14.2.2.1 分析&题解

由于房屋是环形的, 那么对于nums[0, n-1], 若进入过0, 则n-1 无法进入, 反之亦然.

那么可以将问题分解为两个子问题:

• nums[0, n-2]的最优解 A
• nums[1, n-1]的最优解 B

那么最优解就是max(A, B)

迭代 SC: O(1)

TC: O(n)

func rob(nums []int) int {
    n := len(nums)
    // 边界
    if n == 0 {
        return 0
    }
    if n == 1 {
        return nums[0]
    }
    // 两个子问题
    // [0, n-2]
    res1 := robSub(nums[:n-1])
    // [1, n-1]
    res2 := robSub(nums[1:n])

    return max(res1, res2)
}

func robSub(sub []int) int {
    n := len(sub)
    // 缓存
    dp := make([]int, 2)
    // 最小子问题
    if n >= 1 {
        dp[0] = sub[0]
    } 
    if n >= 2 {
        dp[1] = max(sub[0], sub[1])
    }

    for i := 2; i < n; i++ {
        a := (i-2) % 2
        b := (i-1) % 2
        dp[i%2] = max(dp[a]+sub[i], dp[b])
    }

    return dp[(n-1)%2]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

14.2.3 问题91: 粉刷房子

LCR 091. 粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]
输出: 2

提示:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

14.2.3.1 分析&题解

粉刷房子有n步, 每步有多个选择, 求最优解,适用于动态规划.

状态转移方程

房子编号[0, n-1], 对于房子i, 其最少成本, 根据选择不同颜色之后的最小成本为$r(i), g(i), b(i)$:

• 若i选择红色, 那么i-1只能是绿色或蓝色, 最少成本为: $r(i) = min(g(i-1), b(i-1))+cost[i][0]$
• 若i选择绿色, 那么i-1只能是红色或蓝色, 最少成本为: $g(i)=min(r(i-1),b(i-1)+cost[i][1])$
• 若i选择蓝色, 那么i-1只能是红色或绿色, 最少成本为: $b(i)=min(r(i-1),g(i-1)+cost[i][2])$

最终最小成本就是三者中最小的那个.

隐含条件: i>0, 当i`为0时, 最小成本为三种颜色之一, $r(0)=cost[0][0]$ or $g(0)=cost[0][1]$ or $b(0)=cost[0][2]$

迭代 SC O(1)

由于第i+1项结果只和第i项有关, $f(i),f(i+1)$分别存储在i%2, (i+1)%2 的位置, 将会缓存大小为2即可.

func minCost(costs [][]int) int {
    n := len(costs)
    // 边界
    if n == 0 {
        return 0
    }

    // 缓存
    dp := make([][]int, 3)
    // 最小问题
    for i := range dp {
        tmp := make([]int, 2)
        tmp[0] = costs[0][i]
        dp[i] = tmp
    }

    for i := 1; i < n; i++ {
        // 三种颜色
        for j := 0; j < 3; j++ {
            prev1 := dp[(j+2)%3][(i-1)%2] 
            prev2 := dp[(j+1)%3][(i-1)%2]

            dp[j][i%2] = min(prev1, prev2) + costs[i][j]
        }
    }

    // 三种方案中最小的
    last := (n-1)%2
    return min(dp[0][last], min(dp[1][last], dp[2][last]))
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

14.2.4 问题92: 翻转字符

LCR 092. 将字符串翻转到单调递增

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

示例 1：

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

提示：

• 1 <= s.length <= 20000
• s 中只包含字符 '0' 和 '1'

14.2.4.1 分析&题解

达成要求需要多步, 每个步骤有两个选择: 翻转/不翻转, 需要找出最小次数, 适用于动态规划.

状态转移方程

对于字符串[0,i], 第i个字符面临两个选择, 而已满足条件的字符串[0, i-1]也有两个状态:

• [0,i-1]以0结尾, 此时i翻转或不翻转都满足条件, 假设$f(i)$是以0结尾的状态的最优解, 则有:
  • 字符i为0: 不用翻转, $f(i)=f(i-1)$
  • 字符i为1: 需要翻转, $f(i)=f(i-1)+1$
• [0,i-1]以1结尾, 假设最优解$g(i)$:
  • 字符i为0: 需要翻转, $g(i)=min(f(i-1),g(i-1))+1$, 因为i-2可能为0或1, 所以是$f(i-1),g(i-1)$最小的
  • 字符i为1: 不用翻转, $g(i)=min(f(i-1),g(i-1))$

最终结果为$min(f(n-1), g(n-1))$

隐含条件: i>=1, 当i为0是, 只有一个字符:

• 字符i为0: $f(0)=0, g(0)=1$
• 字符i为1: $f(0)=1, g(0)=0$

迭代 SC: O(1)

因为当前最优解之和前一最优解有关, 缓存大小取2.

func minFlipsMonoIncr(s string) int {
    n := len(s)
    if n == 0 {
      return 0
    }

    // 缓存
    // dp[0] 表示翻转后,末尾为0的最优解
    // dp[1] 表示翻转后, 末尾为1的最优解
    dp := make([][]int, 2)
    for i := range dp {
      dp[i] = make([]int, 2)
    }
    // 最小问题
    if s[0] == '0' {
      dp[0][0] = 0
      dp[1][0] = 1
    } else { // s[0] == '1'
      dp[0][0] = 1
      dp[1][0] = 0
    }

    for i := 1; i < n; i++ {
        cur := i % 2
        prev := (i-1) % 2
      if s[i] == '0' {
        dp[0][cur] = dp[0][prev]
        dp[1][cur] = min(dp[0][prev], dp[1][prev]) + 1
      } else { // s[i] == '1'
        dp[0][cur] = dp[0][prev] + 1
        dp[1][cur] = min(dp[0][prev], dp[1][prev])
      }
    }

    last := (n-1) % 2
    return min(dp[0][last], dp[1][last])
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

14.2.5 问题93: 最长斐波那契数列

LCR 093. 最长的斐波那契子序列的长度

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 10^9

14.2.5.1 分析&题解

解决此问题每步都需要选择数字是否将其加入结果数组中使其称为斐波那契数列, 若需要获取所有的结果使用回溯法, 获得最长结果的则使用动态规划.

状态转移方程

若使用$f(i,j)$表示斐波那契数列的长度, 其中数字$N_i, N_j, i < j$ 分别为斐波那契数列中最后两个数字, 那么当前斐波那契数列和前一个$f(k,i)$的关系为:

$f(i,j)=f(k,i)+1$

对于斐波那契数列$f(k,i)$, 添加数字满足$N_j=N_k+N_i, k < i < j$, 就构成了$f(i,j)$.

由于$i<j$, i的取值范围为[0,n-2], j的范围为[1,n-1]

迭代

TC: $O(n^2)$,

SC: $O(n^2)$, 一个二维数组和一个哈希表

func lenLongestFibSubseq(arr []int) int {
	n := len(arr)

	// 哈希表, 快速寻找目标值
	m := make(map[int]int)
	for i, a := range arr {
		m[a] = i
	}

	// 缓存
	// dp[i][j] 表示斐波那契{..., ai, aj}的长度
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	res := 2 // 长度至少为2, 后续才能构成斐波那契数列
	// i: [0, n-2]
	// j: [1, n-1]
	for j := 1; j < n; j++ {
		for i := 0; i < j; i++ {
			ai, aj := arr[i], arr[j]
			k := -1
			// 找出满足 ak + ai = aj 的 k
			if v, ok := m[aj-ai]; ok {
				k = v
			}
			if k != -1 && k < i { // 找到 ak
				dp[i][j] = dp[k][i] + 1
			} else { // ak 不在 ai 之前, {ai, aj} 单独构成, 为后续准备
				dp[i][j] = 2
			}

			res = max(res, dp[i][j])
		}
	}

	if res == 2 {
		res = 0
	}
	return res
}
func max(a, b int) int {
    if a > b {
        return a 
    }
    return b
}

14.2.6 问题94: 最少回文分割

LCR 094. 分割回文串 II

给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

14.2.6.1 分析&题解

// TODO: 2023-09-15

Reference

1. 剑指Offer（专项突破版）