动态规划-钢条切割

问题描述：给定一段长度为n英寸的钢条和价格表p_i（i = 1，2，…，n），求钢条切割方案，使得销售收益r_n最大。主义，如果长度为n英寸的钢条价格p_n足够大，最优解可能就是完全不需要切割。

自顶向下递归实现（Θ(2ⁿ)）

CUT-ROD(p, n){
if n == 0
    return 0
q = -∞
for i = 1 to n
    q = max(q, p[i] + CUT-ROD(p， n-i))
return q
}

使用动态规划方法求解最有钢条切割问题

付出额外内存空间来节省计算时间

带备忘的自顶向下法（Θ(n²)）

MEMOIZED-CUT-ROD(p, n){
let r[0...n] be a new array
for i = 0 to n
    r[i] = -∞
return MEMOIZED-CUT-ROD-AUX(p, n, r)
}

MEMOIZED-CUT-ROD-AUX(p, n, r){
if r[n] >= 0
    return r[n]
if n == 0
    q = 0
else q = -∞
    for i = 1 to n
        q = max(q, MEMOIZED-CUT-ROD-AUX(p, n-i, r))
r[n] = q
return q
}

自底向上法（Θ(n²)）

BOTTOM-UP-CUT-ROD(p, n){
let r[0...n] be a new array
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        q = max(q, p[i] + r[j-i])
    r[j] = q
return r[n]
}

重构解

EXTENDED-BOTTOM-UP-CUT-ROD(p, n){
let r[0...n] and s[0...n] be new arrays
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        if q < p[i] + r[j-i]
            q = p[i] + r[j-i] 
           s[j] = i
    r[j] = q
return r[n]
}

PRINT-CUT-ROD-SOLUTION (p, n){
(r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
while n > 0
    print s[n]
    n = n-s[n]
}

动态规划-矩阵链乘法

问题描述

给定n个矩阵的链<A1，A2，...，An>，矩阵Ai的规模为pi-1xpi（1 <= i <= n），求完全括号化方案，是的计算成绩A1A2...An所需标量乘法次数最少。

一个递归求解方案

image.png

计算最优代价——时间：（Ω(n³)），空间：（Θ(n²)）

MATRIX-CHAIN-PRDER (p){
n = p.length - 1
let m[n, n] and s[n, n] be new tables
for i = 1 to n
    m[i, i] = 0
for i= 2 to n
    for i = 1 to n-l+1
        j = i+l-1
        m[i, j]  = ∞
        for k = i to j-1
            q = m[i, k] + m[k+1 j] + p_i-1*p_k*p_j
            if q < m[i, j]
                m[i, j] = q
                s[i, j] = k
return m and s
}

构造最优解

PRINT-OPTIMAL-PARENS(s, i, j){
if i == j
    print "A"_i
else print "("
    PRINT-OPTIMAL-PARENS(s, i, s[i, j])
    PRINT-OPTIMAL-PARENS(s, s[i, j]+1, j)
    print ")"
}

动态规划-最长公共子序列

问题描述

给定两个序列X=<x₁, x₂, ... , x_m>和Y==<y₁, y₂, ... , y_m>，求X和Y长度最长的公共子序列。

一个递归解

image.png

计算LCS的长度

LCS-ENGTH (X, Y){
m = X.lenght
n = Y.lenght
let b[1...m, 1...n] and c[1...m, 1...n] be new tables
for i = 1 to m
  c[i, 0] = 0
for j = 0 to n
  c[0, j] = 0
for i = 1 to m
  for j = 1 to n
    if x_i == y_i
      c[i, j] = c[i-1, j-1] =1
      b[i, j] = "↖"
    elseif c[i-1, j] >= c[i, j-1]
      c[i, j ] = c[i-1, j]
      b[i, j] = "↑"
    else c[i, j] = c[i, j-1]
      b[i, j] = "←"
reutrn b and c
}

构造LCS

PRINT-LCS (b, X, i, j){
if i == 0 or j == 0
  return
if b[i, j] == "↖"
  PRINT-LCS (b, X, i-1, j-1)
elseif b[i, j] = "↖"
   PRINT-LCS (b, X, i-1, j)
esle b[i, j] = "←"
  PRINT-LCS (b, X, i, j-1)
}