S'S ALGORITHM

动态规划相关问题

动态规划的适用范围

动态规划（Dynamic Programming）是一种解决多阶段决策问题的数学方法，通常用于优化问题。它的核心思想是将原问题分解为若干子问题，通过解决子问题的最优解来得到原问题的最优解。动态规划常用于求解具有重叠子问题和最优子结构性质的问题。动态规划的要点包括：

• 最优子结构：问题的最优解包含了其子问题的最优解。
• 重叠子问题：在递归求解中，相同的子问题会被重复计算，动态规划通过存储已解决的子问题的解来避免重复计算。
• 状态转移方程：定义问题的状态，以及状态之间的转移关系，将问题分解为状态之间的转移。
• 时间复杂度优化：通过避免重复计算，动态规划能够显著降低时间复杂度。
• 空间复杂度增加：为了存储子问题的解，动态规划通常需要额外的空间来存储中间结果。
• 自底向上的计算顺序：动态规划通常采用自底向上的方式求解，即先求解较小规模的子问题，逐步推导出较大规模问题的解。

自上而下和自下而上的解决问题方法的不同：

• 自上而下（Top-down）：也称为记忆化搜索（Memoization），通过递归的方式解决问题，将子问题的解存储在一个数据结构中，避免重复计算。
• 自下而上（Bottom-up）：从最小规模的子问题开始，逐步计算更大规模问题的解，直到求解出原问题的解。通常采用迭代的方式实现，不需要递归调用，因此在空间和时间上都比自上而下的方法更有效率。

动态规划广泛应用于各种领域的优化问题，如：

• 路径规划：如最短路径问题和最优路径问题。
• 资源分配：如背包问题和资源调度问题。
• 序列比对：如DNA序列比对和字符串匹配。
• 金融领域：如股票交易策略优化和期权定价等。
• 负载均衡器：通过使用具有不同工作负载处理能力的服务器来找到处理给定工作负载的最佳方法。
• 搜索引擎：检查是否可以在查询中添加空格以创建有效的单词，以防原始查询在网络上没有得到任何点击。查找可以通过向原始查询添加空格来创建的所有可能的查询。

问题1:N-th Tribonacci Number

是斐波那契数列问题的变形。Tribonacci 序列类似于斐波那契数列的数列，其定义如下：

• Tribonacci 序列的前三个数为 0、1、1。
• 之后的每个数是前三个数的和，即第 n 个数等于第 n-1、n-2 和 n-3 个数的和。

因此，问题的核心是要计算第 N 个 Tribonacci 数，即 T(N)。可以使用动态规划来解决这个问题，可以采用自底向上的方法，逐步计算得到。

基本步骤如下：

• 初始化数组或变量，存储 Tribonacci 序列的前三个数。
• 通过迭代计算从第四个数开始直到第 N 个数的值，每次计算时都根据递推公式 T(n) = T(n-1) + T(n-2) + T(n-3)计算得到当前数的值。
• 最终得到第 N 个 Tribonacci 数的值。

代码尝试：

def find_tribonacci(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        dp = [0] * (n + 1)
        dp[1] = dp[2] = 1
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        return dp[n]

题解给的参考答案：

def find_tribonacci(n):
    if n < 3:
        return 1 if n else 0

    first_num, second_num, third_num = 0, 1, 1
    for _ in range(n - 2):
        first_num, second_num, third_num = second_num, third_num, \
          first_num + second_num + third_num
    return third_num

题解给的答案是一种迭代，关于for循环的地方我更喜欢从 3 开始遍历，感觉比较好理解，所以我更喜欢下面这种迭代写法：

def tribonacci_iterative(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        a, b, c = 0, 1, 1
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c
        return c

学习笔记：时间复杂度上哪种思路都需要遍历全部，所以是O(n)，空间复杂度上迭代法只用了三个变量所以是O(1)，而我一开始的dp数组法则需要储存所有的计算变量，所以为O(n)。

问题2:Counting Bits

计算机科学领域中的一个经典问题。题目要求你对给定的非负整数范围内的每个数字，计算其二进制表示中包含的1的个数。

举个例子，如果范围是0到5，那么对应的二进制表示分别是：

• 0: 0 (0个1)
• 1: 1 (1个1)
• 2: 10 (1个1)
• 3: 11 (2个1)
• 4: 100 (1个1)
• 5: 101 (2个1)

因此，对于范围内的每个数字，你需要计算其二进制表示中1的个数，并将结果存储在一个数组中返回。

解题步骤：

• 创建一个长度 n + 1 的数组。
• 从 0 到 n 顺序计算每个数字的二进制表达以及 1 的个数。存储结果到数组。
  • 计算过程涉及到二进制的offset位移操作。
• 遍历结束，返回数组。

当列举出0-10的所有二进制，就可以找到offset的规律：

0:  0000  0
1:  0001  dp[i - 1] + 1  -> 1
2:  0010  dp[i - 2] + 1  -> 1
3:  0011  dp[i - 2] + 1  -> 2
4:  0100  dp[i - 4] + 1  -> 1
5:  0101  dp[i - 4] + 1  -> 2
6:  0110  dp[i - 4] + 1  -> 2
7:  0111  dp[i - 4] + 1  -> 3
8:  1000  dp[i - 8] + 1  -> 1
9:  1001  dp[i - 8] + 1  -> 2
10: 1010  dp[i - 8] + 1  -> 2
11: 1011  dp[i - 8] + 1  -> 3
12: 1100  dp[i - 8] + 1  -> 2
13: 1101  dp[i - 8] + 1  -> 3
14: 1110  dp[i - 8] + 1  -> 3
15: 1111  dp[i - 8] + 1  -> 4
16: 10000 dp[i - 16] + 1 -> 1
17: 10001 dp[i - 16] + 1 -> 2
18: 10010 dp[i - 16] + 1 -> 2
19: 10011 dp[i - 16] + 1 -> 3
20: 10100 dp[i - 16] + 1 -> 2

可以看到offset在1， 2， 4， 8的时候和i相等。而每一次offset变化，都是比前一个offset增加一倍。那么只需要动态调整计算offset的数值，就可以用动态规划算法解答了。

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

第二种方法也是使用了递推，是根据奇偶的递推，也是这道题给的题解。

def counting_bits(n):
    # 创建一个数组用于存储结果，初始值都为0
    result = [0] * (n + 1)  # 创建长度为 n+1 的数组，初始化为0

    # 如果 n 为0，直接返回结果数组
    if n == 0:
        return result

    # 设置 0 和 1 的二进制表示中的1的个数
    result[0] = 0
    result[1] = 1

    # 遍历从2到n的每个数字
    for x in range(2, n + 1):
        # 如果 x 是偶数
        if x % 2 == 0:
            # 则 x 的二进制表示中的1的个数与 x//2 的二进制表示中的1的个数相同
            result[x] = result[x // 2]
        else:
            # 如果 x 是奇数，则 x 的二进制表示中的1的个数为 x//2 的二进制表示中的1的个数加1
            result[x] = result[x // 2] + 1

    # 返回结果数组
    return result

这段代码的作用是计算从0到n的每个数字的二进制表示中1的个数，并将结果存储在一个数组中返回。

• 创建一个长度为n+1的数组，初始化为0，用于存储每个数字的二进制表示中1的个数。
• 如果n为0，直接返回结果数组。
• 设置0和1的二进制表示中的1的个数为0和1。
• 对于每个从2到n的数字：
  • 如果该数字是偶数，则其二进制表示中1的个数与该数字除以2的二进制表示中1的个数相同。
  • 如果该数字是奇数，则其二进制表示中1的个数为该数字除以2的二进制表示中1的个数加1。
• 返回结果数组。

第三种方法是用按位与符号，进行递推。

def counting_bits(n):
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        # 通过 i & (i - 1) 可以得到 i 的二进制表示中最低位的1变为0后的值
        # 这样就可以利用之前已经计算过的结果 result[i & (i - 1)]，并在其基础上加1
        result[i] = result[i & (i - 1)] + 1
    return result

• 我们使用位操作 i & (i - 1) 来获取当前数字 i 去掉最低位1后的结果。这是因为，当我们去掉最低位1后，得到的数字一定比原来的数字小，并且其二进制表示中1的个数已经在之前的迭代中计算过了。
• 我们利用 result[i & (i - 1)] 来获取去掉最低位1后的数字的二进制表示中1的个数，并在其基础上加1，即 result[i & (i - 1)] + 1。这样就得到了当前数字的二进制表示中1的个数。
• 按位与操作的规则是对应位上的数字如果都是1，则结果中对应位为1，否则为0。因此，当我们对一个数 i 和 i - 1 进行按位与操作时，会将 i 的二进制表示中的最低位的1变为0，而其他位保持不变。

学习笔记：时间复杂度为一次遍历O(n)，空间复杂度为O(1)。应当熟悉的计算机基础。

问题3:Word Break II

经典的动态规划问题，给定一个非空字符串和一个字符串字典，字典中的单词没有重复。要求根据字典中的单词将给定字符串分割成一系列符合要求的子字符串，并返回所有可能的分割结果。

例如，给定字符串 s = “catsanddog” 和字典 wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]，一个可能的分割结果是 [“cats and dog”, “cat sand dog”]。

动态规划算法通常用于解决这类问题。下面是解题思路：

• 状态定义：定义一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符能否被拆分成符合要求的子字符串。另外，定义一个哈希集合（或字典）存储字典中的单词。
• 状态转移方程：对于每个位置 i，遍历 j（0 <= j < i），如果 dp[j] 为 true 且 s[j:i] 在字典中，那么 dp[i] 也为 true。
• 回溯：使用回溯算法从 dp 数组中获取所有可能的分割结果。具体实现时，可以使用递归函数，对每个位置 i，递归搜索以 i 为起点的所有可能分割方案。
• 返回结果：返回所有可能的分割方案。

这种方法的时间复杂度取决于单词字典的大小和字符串的长度，通常为 O(n^3)。因此，在实际解题中，可能需要结合优化技巧（如记忆化搜索）来提高效率。

代码如下：

def word_break(s, word_dict):
    wordset = set(word_dict)

    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordset:
                dp[i] = True
                break

    def backtracking(start, path):
        if start == len(s):
            res.append(" ".join(path))
            return

        for end in range(start + 1, len(s) + 1):
            if dp[end] and s[start:end] in wordset:
                backtracking(end, path + [s[start:end]])

    res = []
    if dp[len(s)]:
        backtracking(0, [])

    return res

学习笔记：这道题的第一个部分的dp数组，其实是第139道leetcode题word break的解答，是一道中等难度题，当然这道139还有别的解法。而这道变体是140题，hard难度。如果觉得这道题难可以从139着手。

在这个算法中，动态规划的时间复杂度为 O(n^2)，其中 n 是字符串的长度。这是因为我们需要遍历字符串的每个字符，对于每个字符，又需要遍历之前的所有字符来确定是否可以进行拆分。在动态规划的过程中，每个位置的状态都只需计算一次，因此总的时间复杂度为 O(n^2)。

回溯的时间复杂度取决于所有可能的分割方案的数量。在最坏情况下，即字典中的单词长度都很小，导致可以拆分的方案数量指数增长，回溯的时间复杂度为 O(2^n)，其中 n 是字符串的长度。但是，由于我们使用了动态规划预处理字符串是否可以拆分，可以减少回溯的次数，因此实际的时间复杂度会小于 O(2^n)。

空间复杂度方面，动态规划数组的长度为 n+1，因此空间复杂度为 O(n)。回溯过程中使用的递归栈的空间复杂度也为 O(n)，因为在最坏情况下可能需要递归调用 n 层。另外，我们还需要使用额外的空间存储字典中的单词集合，但通常这个额外空间的大小可以忽略不计。因此，总的空间复杂度为 O(n)。

另外题解给出的代码答案：这个答案很棒。不需要回溯。

def word_break(s, word_dict):
    dp = [[]] * (len(s) + 1)
    dp[0] = [""]

    for i in range(1, len(s) + 1):
        prefix = s[:i]
        temp = []

        for j in range(0, i):
            suffix = prefix[j:]
            if suffix in word_dict:
                
                for substring in dp[j]:
                    temp.append((substring + " " + suffix).strip())

        dp[i] = temp

    return dp[len(s)]

• 这个方法使用了动态规划来预处理字符串的所有可能的分割方案，从而避免了重复计算，提高了效率。
• 通过逐步构建动态规划数组，可以在最后一步直接获取到字符串的所有分割方案，而不需要进行回溯操作。

时间复杂度：由于需要遍历字符串每个字符，对于每个字符，又需要遍历其所有可能的后缀子串，并检查是否在字典中。因此，时间复杂度为 O(n^2 * m)，其中 n 是字符串的长度，m 是字典 word_dict 中单词的平均长度。

空间复杂度：动态规划数组 dp 的长度为 len(s) + 1，而且对于每个位置 i，需要存储一个包含所有可能分割方案的列表。因此，空间复杂度为 O(n * m)，其中 n 是字符串 s 的长度，m 是字典 word_dict 中单词的平均长度。