Dynamic programming

learning

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

steps:

1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
4. Construct an optimal solution from computed information.

Example 1 Rod cutting

Given a rod of length n inches and a table of prices $p_i$ for $i=1,2 ,...,n$，determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the prices.

maximum revenue $r_n=max(p_n,r_1+r_{n-1}，r_2+r_{n-2},...,r_{n-1}+r_n)$

Recursive top-down implementation

static int k=0;
int cutrod(int p[],int n)
//p为每个长度的价格，n为长度  
//q为输出，保存每个长度的最优价格  
{
    if(n==0)
        return 0;
    int q=0;
    for(int i=0;i<n;i++)
       q=MAX(q,p[i]+cutrod(p,n-i-1));
    k++;
    cout<<q<<" ";//输入每次调用函数保存的最优价格
    return q;
}

输出结果：

enter the length of steer:4
1 5 1 8 1 5 1 10 
the times of recursion:8

CUT-ROD calls itself recursively over and over again with the same parameter value; it solves the same subproblems repeatedly.

top-down with memoization

static int k=0;
int memoized_cut_rod_aux(int p[],int n,int r[])
{
    if (r[n]>=0)
        return r[n];
    int q;
    if (n==0)
        q=0;
    else
        {
            q=-1;
            for(int i=0;i<n;i++)
                q=max(q,p[i]+memoized_cut_rod_aux(p,n-i-1,r));
        }
    r[n]=q;  //保存子问题的解
    k++;        //计算递归次数
    cout<<q<<"  ";
    return q;
}
int memoized_cut_rod(int p[],int n)
{
    int *r=new int [n+1];
    for(int i=0;i<=n;i++)
        r[i]=-1;
    return memoized_cut_rod_aux(p,n,r);
}

输出结果：

enter the length of steer:4
0  1  5  8  10  
the times of recursion:5

bottom-up method

int bottom_up_cut_rod(int p[],int n)
{
    int *r=new int [n+1];
    r[0]=0;
    for(int j=1;j<=n;j++)
    {
        int q=-1;
        for(int i=0;i<j;i++)
            q=max(q,p[i]+r[j-i-1]);
        r[j]=q;
    }
    return r[n];
}

输出结果：

enter the length of steer:4
the maximum revenue:10

example 2 matrix chain

Given a sequence (chain) $<A_1,A_2,,...,A_n>$ of n matrix to be multiplied, and we wish to compute the product $A_1A_2...A_n$.

• Step 1: The structure of an optimal parenthisization
  Adopt the notation $A_{i...j}$, where $i\le j$, for the matrix that results from evaluating the product $A_iA_{i+1}...A_j$ and split the product between $A_k$ and $A_{k+1}$ for some integer $k$ in the range $i\le k\le j$.
• Setp 2: A recursive solution
  Let m[i,j] be the minimum number of scalar multiplications needed to compute the matrix $A_{i...j}$
  if $i=j$, $m[i,j]=0$
  if $i<j$, $m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}p_kp_j$
• compute the optimal costs
  Adopt another auxiliary table $s[1..n-1,2..n]$ that records which index of $k$ achieved the optimal cost in computing $m[i,j]$.

void Matrix_Chain_Order(int* p,int **m,int** s)
{
    //矩阵链的长度  
    int n = sizeof(p)/sizeof(p[0])-1;
    //①将对角线上的值先赋值为0  
    for (int i = 1; i <= n; i++) 
    {
        m[i][i] = 0;
    }
    int l = 0; //l为矩阵链的长度  
    //m[i][j]的第一个参数  
        int i = 0;
    //m[i][j]的第二个参数  
    int j = 0;
     //②以长度L为划分，L从2开始到n  
    for (l = 2; l <= n; l++) 
    {
        //循环第一个参数，因为l的长度至少为2，所以i和j在这个循环里面肯定不相等  
        for (i = 1; i <= n - l + 1; i++)
        {
            //因为j-i+1=l，所以j=l+i-1  
            j = i + l - 1;
            //对于每个特定的i和j的组合，遍历此时所有的合适k值，k大于等于i小于j  
            for (int k = i ; k < j; k++)
            {
                 //这里k不能等于j，因为后面要m[k+1][j]，不然k+1就比j大了  
                int 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;
                }
            }
        }
    }
}

• Step 4: constructing an optimal solution

void print_optimal_parens(int** s, int i, int j)
{
    if (i == j) 
    {
        cout << "A" << i;
    } 
    else 
    {
        cout << "(";
        print_optimal_parens(s, i, s[i][j]);
        print_optimal_parens(s, s[i][j] + 1, j);
        cout << ")";
    }
}

example 3 Longest common subsequence

Given two sequences $X=<x_1,x_2,...,x_m>$ and $Y=<y_1,y_2,...,y_n>$ and wish to find maximumlength common subsequence of X and Y.

• Step 1: Characterizing a longest common subsequence
  Theorem : Let $X=<x_1,x_2,...,x_m>$ and $Y=<y_1,y_2,...,y_n>$ be sequences, and let $Z=<z_1,z_2,...,z_k>$ be any LCS of X and Y.
  
  1. if $x_m=y_n$, then $z_k=x_m=y_n$ and $Z_k-1$ is an LCS of $X_{m-1}$ and $Y_{n-1}$
  2. if $x_m\not=y_n$, then $z_k\not=x_m$ implies that Z is an LCS of $X_{m-1}$ and Y
  3. if $x_m\not=y_n$, then $z_k\not=y_n$ implies that Z is an LCS of X and $Y_{n-1}$
• Step 2: A recursive solution
  Define $c[i,j]$ to be the length of an LCS of the sequences $X_i$ and $Y_j$.

$c[i,j] = \begin{cases} 0, & \mbox{if }i=0\mbox{ or }j=0 \\ c[i-1,j-1], & \mbox{if }i,j>0\mbox{ and }x_i=y_j\\ max(c[i,j-1],c[i-1,j), &\mbox{if }i,j>0\mbox{ and }x_i\not=y_j \end{cases}$

• Step 3: Computing the length of an LCS

  $b[i][j]=1$相当于$\nwarrow$
  $b[i][j]=2$相当于$\uparrow$
  $b[i][j]=3$相当于$\downarrow$

void LCSLength(int m,int n,char *x,char *y,int **c,int **b)  
{  
//x和y是目标序列
//m是x的长度，n是y的长度
    int i,j;  
  //当x或y为空序列时，无公共子序列
    for(i=1; i<=m; i++)  //x长度为i，y长度为j
        c[i][0] = 0;  
    for(i=1; i<=n; i++)  
        c[0][i] = 0;  
    for(i=1; i<=m; i++)  
    {  
        for(j=1; j<=n; j++)  
        {  
            if(x[i]==y[j])  
            {  
                c[i][j]=c[i-1][j-1]+1;  
                b[i][j]=1;      
            }  
            else if(c[i-1][j]>=c[i][j-1])  
            {  
                c[i][j]=c[i-1][j];  
                b[i][j]=2;  
            }  
            else  
            {  
                 c[i][j]=c[i][j-1];  
                 b[i][j]=3;  
            }  
        }  
    }  
}

• Step 4: Constructing an LCS

void LCS(int i,int j,char *x,int **b)  
{  
    if(i==0 || j==0)  
    {  
        return;  
    }  
    if(b[i][j]==1)  
    {  
        LCS(i-1,j-1,x,b);  
        cout<<x[i]<<" ";  
    }  
    else if(b[i][j]==2)  
    {  
        LCS(i-1,j,x,b);  
    }  
    else  
    {  
        LCS(i,j-1,x,b);  
    }  
}

Improving the code

int LCS(string sx, string sy)  
{  
    int sizex = sx.length();  
    int sizey = sy.length();  
    //创建动态二维数组  
    int **lcs = new int*[sizex];  
    for (int i = 0; i < sizex; i++)  
    {     
        lcs[i] = new int[sizey];  
    }  
    //求解LCS  
    int max = 0;  
    for (int i = 0; i < sizex; i++)  
    {  
        for (int j = 0; j < sizey; j++)  
        {  
            //计算初始值：lcs[0][x]和lcs[x][0]的值  
            if (i == 0 || j == 0)  
            {  
                if (sx[i] == sy[j])  
                {  
                    lcs[i][j] = 1;  
                }  
                else  
                {  
                    if (i == 0 && j == 0)  
                        lcs[i][j] = 0;  
                    else if (i == 0 && j != 0)  
                        lcs[i][j] = lcs[i][j-1];  
                    else  
                        lcs[i][j] = lcs[i-1][j];  
                }  
            }  
            else  //其他lcs[i][j]的值  
            {  
                if (sx[i] == sy[j])  
                    lcs[i][j] = lcs[i-1][j-1] + 1;  
                else   
                    lcs[i][j] = lcs[i-1][j] > lcs[i][j-1] ? lcs[i-1][j] : lcs[i][j-1];  
            }  
            if (lcs[i][j] > max)   
                max = lcs[i][j];  
        }  
    }  
    //释放动态二维数组  
    for (int i = 0; i < sizex; ++i)  
    {  
        delete[] lcs[i];  
    }  
    delete[] lcs;  
    return max;  
}  

example 4 Optimal binary search trees

$k_i$ : key
$p_i$ : the probability of $k_i$
$d_i$ : the dummy key which represents all values between $k_i$ and $k_{i+1}$
$q_i$ : the probability of $d_i$

Every search is either successful (finding some key $k_i$) or unsuccessful (findng some dummy key $d_i$).
$\sum\limits_{i=1}^{n} p_i+\sum\limits_{i=0}^n q_i=1$
E [Search cost in T} $=\sum\limits_{i=1}^n(depth_T(k_i)+1).p_i+\sum\limits_{i=0}^n(depth_T(d_i)+1).q_i$
$=1+\sum\limits_{i=1}^ndepth_T(k_i).p_i+\sum\limits_{i=0}^ndepth_T(d_i).q_i$

• Step 1: The structure of an optimal binary search tree
  If an optimal binary search tree T has a subtree $T^`$ containing keys $k_i,...,k_j$, then this subtree $T^`$ must be optimal as well for the subproblem with keys $k_i,...,k_j$ and dummy keys $d_{i-1},...,d_j$.
• Step 2: A recursive solution
  Define $e[i,j]$ as the expected cost of searching an optimal binary search tree containing the keys $k_i,...,k_j$.
  When $j=i-1$,the expected search cost is $e[i,j]=q_{i-1}$
  When $j\ge i$, the depth of each node in the subtree increases by the sum of all the probabilities in the subtree. The sum of probabilities as $w(i,j)=\sum\limits_{l=i}^jp_i+\sum\limits_{l=i-1}^jq_i$
  If $k_r$ is the root if an optimal subtree containing keys $k_i,...,k_j$,
  $e[i,j]=p_r+(e[i,r-1]+w[i,r-1])+(e[r+1,j]+w[r+1,j])$
  $w[i,j]=w[i,r-1]+p_r+w[r+1,j]$
  $e[i,j]e[i,r-1]+e[r+1,j]+w[i,j]$
  $e[i,j] = \begin{cases} q_{i-1}, & \mbox{if }j=i-1 \\ min(e[i,r-1]+e[r+1,j]+w[i,j]), &\mbox{if }i\le j \end{cases}$
• Step 3: Computing the expected search cost of an optimal binaty search tree

copy
void OPTIMAL_BST(int *p,int *q,int n,int **e,int **w,int **root)  
{  
//初始化只包含虚拟键的子树
    for(int i=1;i<=n+1;i++)  
    {  
        e[i][i-1]=q[i-1];  
        w[i][i-1]=q[i-1];  
    }  
    for(int l=1;l<=n;l++)         
    {  
        for(int i=1;i<=n-l+1;i++)  
        {     
            j=i+l-1;  
            e[i][j]=INT_MAX;  
            w[i][j]=w[i][j-1]+p[i]+q[j];  //字数期望概率总和
            for(int r=i;r<=j;r++)  
            {  
                int t=e[i][r-1]+e[r+1][j]+w[i][j];  
                if(t<e[i][j])  
                {  
                    e[i][j]=t;       //字数期望代价
                    root[i][j]=r;    //记录根节点
                }  
            }  
        }  
    }  
}