动态规划练习-切棍子与最长子序列

1. 切棍子

题目:

给出棍子的价格 p(i), 其中i代表棍子的长度. 考虑一个长度为n的棍子, 如何切割才能达到总价值最大. 并且每次切割都会花费固定的费用c. 要求用动态规划的方法.

答:

• 思路:
  1. 对于长度为n的棍子, 如果用暴力法, 那么时间复杂度大概是2^(n-1).
  2. 考虑动态规划, 那么最优子结构是把一个棍子一分为2, 一直分下去到长度为0
  3. 自底向上. 分别遍历从长度0到长度n的情况下的价值, 因为大的长度依赖小的长度, 所以把较小长度最大价值记录下来, 就能快速算出较大长度的价值. 同时也避免了一个较小长度多次计算的耗时问题.
• 伪代码:

MODIFIED-CUT-ROD(p, n, c) // p是数组, 代表不同长度的不同价格. 
    let r[0..n] be a new array // 用来分别存储0-n长度的最大价值
    r[0] = 0  // 长度为0, 价值自然也是0
    for j = 1 to n // 自底向上分别求出各个长度的最大价值
        q = p[j] // 不切割情况下的价值
        for i = 1 to j - 1 // 遍历从各个位置切割的情况
            q = max(q, p[i] + r[j - i] - c) // 算出指定位置切割下的价值, 并且和最大值比较, 如果大, 就替换为最大价值
        r[j] = q
    return r[n]

2. 最长子序列

题目1:

求序列⟨1,0,0,1,0,1,0,1⟩ 和 ⟨0,1,0,1,1,0,1,1,0⟩最长子序列

答:

• 思路:
  1. 先看是否能拆分为子问题. 如果两个序列的最后一个数字相等, 那么可以把问题缩减为求原长度减去最后一个数字的问题, 最后加1就好; 如果最后一个数字不等, 那么就等价于求其中一个序列和另外一个序列中减掉最后一个数字的问题.由此可看出, 可以把大规模拆分为小规模来求解.

• 自底向上的图解:

  
  image.png
• 最长子序列不止一个, 最大长度为6.

题目2:

给定一个字符串, 求出最长子序列, 要求子序列单调递增, 并且算法时间复杂度为O(n^2)

答:

• 思路:
  1. 暴力解决法: 拆分出每一个子序列, 查看是否满足递增特性, 选出最大的一个. 时间复杂度为指数时间, 不符合题意.
  2. 把给定的字符串排序好, 然后求出两个字符串的最长子串, 把问题转化为和有序的字符串求最长子串问题, 这样求出来的肯定是单调有序的. 排序时间复杂度最大在n^2, 用动态规划求解最长子串也在O(n^2), 所以满足题目意思.
• 伪代码

PRINT-LCS(c, X, Y)
    n = c[X.length, Y.length]
    let s[1..n] be a new array
    i = X.length
    j = Y.length
    while i > 0 and j > 0
        if x[i] == y[j]
            s[n] = x[i]
            n = n - 1
            i = i - 1
            j = j - 1
        else if c[i - 1, j] ≥ c[i, j - 1]
            i = i - 1
        else j = j - 1
    for i = 1 to s.length
        print s[i]

MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    m = |X|
    n = |Y|
    if c[m, n] != 0 or m == 0 or n == 0
        return
    if x[m] == y[n]
        b[m, n] = ↖
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y[1..n - 1], c, b) + 1
    else if MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) ≥ MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
        b[m, n] = ↑
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b)
    else
        b[m, n] = ←
        c[m, n] = MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)