L17&L18 DP

Posted on Edited on In Views:

Outline:

  • Basic Idea of Dynamic Programming(DP)
    • Smart scheduling of subproblems
  • Minimum Cost Matrix Multiplication
    • BF1, BF2
    • A DP solution
  • Weighted Binary Search Tree
    • The "same" DP with matrix multiplication
  • From the DP perspective
    • All-pairs shortest paths SSSP over DAG
  • More DP problems
    • Edit distance
    • Highway restaurants; Separating Sequence of words
    • Changing coins
  • Elements of DP

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇

Basic Idea of DP

  • Smart recursion
    • Compute each subproblem only once
  • Basic process of a "smart" recursion
    • Find a reverse topological order for the subproblem graph
      • In most cases, the order can be determined by partial knowledge of the problem.
      • General method based on DFS is available.
    • Scheduling the subproblems according to the reverse topological order
    • Record the subproblem solutions in a dictionary.

Minimum Cost Matrix Multiplication

BF1

  • 总是在某个位置开始第一次乘法
1
2
3
4
5
6
7
8
9
10
mmTry1(dim,len,seq)
    if(len < 3) bestCost = 0;
	else
        bestCost = ∞;
		for(i=1; i < len ; i++ )
            c=cost of muliplication at position seq[i];
			newSeq = seq with ith element deleted;
			b= mmTry1(dim, len-1, newSeq);
			bestCost=min(bestCost, b+c);
	return bestCost;
  • \(T(n)= (n-1)T(n-1)+n\)
  • \(\Theta( (n-1)! )\)

BF2

  • 必然在某个位置k相乘
  • BF1“总是在某个位置开始第一次乘法”，子问题规模下降过慢
1
2
3
4
5
6
7
8
9
10
mmTry2(dim, low,high)
	if(high - low == 1 ) bestCost=0; //only one matrix
	else
		bestCost = ∞
		for( k = low + 1; k < high; k++ )
			a = mmyTry2(dim, low,k);
			b = mmyTry2(dim, k, high);
            c = cost of multiplication at position k;
            bestCost = min(bestCost,a+b+c);
    return bestCost;
  • \(W(n)=2W(n-1)+n\)
  • \(O(2^n)\)

A DP solution

1
2
3
4
5
6
7
8
matrixOrder(n,cost,last) //last记的是位置
	for( low=n-1; low > 1; low-- )//按行，从下往上填
		for(high-low+1; high <= n; high++ )//按列，从左往右填
			Compute solution of subproblem ( low,high  ) and store it in cost[low][high] 				and last[low][high]
			
	return cost[0][n]
  • 时间 \(\Theta(n^3)\)​
  • 空间 \(\Theta(n^2)\)

Weighted Binary Search Tree

  • 规定\(A(T) = \sum\limits_{i=1}^n {p_ic_i}\)​, 其中\(c_i = depth(i) + 1\)​， \(p_i\)​是节点i被访问到的概率。 如何优化WBST使得A(T)最小？

Problem Rephrased

  • Subproblem identification
    • The keys are in sorted order
    • Each subproblem can be identified as a pair of index (low,high)
  • Expected solution of the subproblem
    • For each key \(K_i\), a weight \(p_i\) is associated.
      • \(p_i\)​ is the possibility that the key is searched for
    • The subproblem (low,high) is to find the binary search tree with minimum weighted retrieval cost

minimum weighted retrieval cost

  • A(low,high,r) is the minimum weighted retrieval cost for subproblem (low,high) where \(K_r\)​ is chosen as the root of its BST​
  • A(low,high) is the minimum weighted retrieval cost for subproblem (low,high) over all choices of the root key
  • p(low,high), equal to \(p_{low} + p_{low+1} + \dots + p_{high}\) is the weight of the subproblem (low,high)
    • p(low,high) is the possibility that the key searched for is in this interval.

Subproblem solutions

  • Weighted retrieval cost of a subtree

    • T contains \(K_{low}, \dots, K_{high}\)​​, and the weighted retrieval cost of R is W, with T being a whole tree.

    • As a subtree with the root at level 1, the weighted retrieval cost of T will be : \(W + p(low,high)\)​

      • \(p(low,high)\)​是子问题并入大问题时所付出的代价（修正量）,即 “whole tree”变成子树所付出的修正量

      • \(\sum\limits_{i=1}^{n}(p_i . (c_i + 1)) = \sum\limits_{i=1}^n {p_ic_i} + \sum\limits_{i=1}^{n}p_i = W + p(low,high)\)​

    • 根\(K_r\)​的代价是\(p_{r}\)​

  • So， the recursive relations are:

    \(A(low,high,r) \\ = p_r + p(low,r-1) + A(low,r-1) + p(r+1, high) + A(r+1, high)\\ = p(low,high) + A(low,r-1)+A(r+1,high)\)

    • \(A(low,high) = min{ A(low,high,r) | \quad low \leq r \leq high}\)
1
2
3
4
5
optimalBST( prob,n,cost,root )
	for(low=n+1; low >= 1; low-- )
		for(high=low-1; high <= n; high++)
			bestChoice(prob,cost,root,low,high);
	return cost;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bestChoice(prob,cost,root,low,high)
	if(high < low )
		bestCost=0;
		bestRoot=-1;
	else
		bestCost = ∞;
	for( r = low; r <= high ; r++ )
		rCost = p(low,high) + cost[low][r-1]+cost[r+1][high];
		if(rCost < bestCost)
			bestCost = rCost;
			bestRoot=r;
		cost[low][high]=bestCost;
		root[low][high]=bestRoot;
    return
  • \(\Theta(n^3)\)

From the DP perspective

All-pairs shortest paths SSSP over DAG

\(D.dis = min\{ B.dis + 1, C.dis+3 \}\)

Highway restaurants

  • Highway restaurants
    • n possible locations on a straight line
      • \(m_1,m_2,m_3,\dots,m_n\)
    • At most one restaurant at one location
      • Expected profit for location i is \(p_{i}\)
    • Any two restaurants should be at least k miles apart
  • How to arrange the restaurants
    • To obtain the maximum expected profit
  • The recursion
    • P(j): the max profit achievable using only first j locations 只开若干个餐厅,其中最大序号为j, 所获得的利润
      • P(0) = 0
    • prev[j]: largest index before j and k miles away

\[ P(j) = max( p_j + P(prev[j]),P(j-1) ) \]

  • One dimension DP algorithm
    • Fill in P[0],P[1], ... , P[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
(First compute the prev[.] array)  //预处理
i = 0
for j = 1 to n:
	while m_{i+1} <= m_{j} - l: // m[i]是第i个餐厅的位置
		i = i+1;
	prev[j] = i; // 预处理结束
	
(Now the DP begins)
P[0]=0;
for j = 1 to n:
	P[j] = max( p_j + P[prev[j]], P[j-1] );
return P[n];

Separating Sequence of words

  • Words into lines:
    • Word-length \(w_1, w_2, \dots, w_n\) and line-width: W
  • Basic constraint
    • If \(w_i, w_{i+1}, \dots, w_j\) are in one line, then \(w_i, w_{i+1}, \dots, w_j \leq W\)
  • Penalty for one line: some function of X, X is:
    • 0 for the last line in a paragraph, and
    • \(W-(w_i, w_{i+1}, \dots, w_j)\) for other lines
  • The problem
    • How to make the penalty of the paragraph, which is the sum of the penalties of individual lines, minimized
1
2
3
4
5
6
7
8
9
10
11
12
13
LineBreakDP

for i = n; i >= 1; i--:
	if all words through w_i to w_n can be put into one line then:
		Penalty[i] = 0;
		<put all words through i yo n in one line>
	else 
		for i=1; w_i + ... + w_{i+k-1} <= W; k++:
			calculate the penalty Cost_{cur} of putting words in this line;
			minCost = min{minCost,Cost_{cur} + Penalty[ i+k ]};
			<Updating k_{min}, which records the k part that produced the minimun penalty>;
			<Put words i through i + k_{min}> - 1 on one line;
	Penalty = minCost;

Analysis of LineBreakDP

  • Each subproblem is identified by only one integer k, for (k,n)
    • Number of vertex in the subproblem graph: at most n
    • So, in DP version, the recursion is executed at most n times.
  • So, the running time is in \(\Theta(Wn)\)
    • The loop is executed at most W/2 times. //每个单词后都有空格,标点
    • In fact, W, the line width, is usually a constant. So, \(\Theta(n)\)
    • The extra space for the dictionary is \(\Theta(n)\)

Changing coins

  • How to pay a given amount of money?

  • 贪心不行

Subproblems

  • Assumptions

    • Given n different denotations
    • A coin of denomination i has \(d_{i}\)​ units 面额为i的硬币代表了\(d_{i}\)的金钱
    • The amount to be paid: N

  • Subproblems [i,j]

    • The minimum number of coins required to pay an amount of j units, using only coins of denominations 1 to i.

  • The problem

    • Figure out subproblems [ n, N ] ( as c[n, N] )

  • 易得:

  • c[i,0] is 0 for all i

  • \(c[i,j]=min\{c[i-1,j], 1+ c[1+c[i,j-d_i]\}\)

1
2
3
4
5
6
7
8
9
10
11
int coinChange( int N, int n, int[] coin)
    int denomination[] = [d_1, d_2, ..., d_n];
	for(i=1; i<=n; i++)
        coin[i,0]=0;
	for(i=1;i<=n;i++)
        for(j=1;j<=N;j++)
            if( i == 1 && j <denomination[i] ) coin[i,j] = + ∞; //只有一个硬币且面额大于所需金额,不满足
			else if( i == 1 ) coin[i,j] = 1 + coin[1, j - denomination[1]];//只有一个硬币,其面额小于等于所需金额
			else if(j < denomination[i]) coin[i,j] = coin[i-1,j];//不止一个硬币,最后一枚的面额大于所需金额, 则剔除这枚硬币
			else coin[i,j] = min( coin[i-1,j], 1 + coin[j-denomination[i]] );
	return coin[n,N];

Elemens of DP

Principle of Optimality

  • 重叠子问题
  • 蛮力找最优
  • Optimal substructure: 大问题的最优解必然由小问题的最优解组合而成.
    • Given an optimal sequence of decisions, each subsequence must be optimal by itself
    • Positive example: shortest path
    • Counter example: longest (simple) path
    • DP relies on the principle of optimality