L17&L18 DP

Posted on 2021-08-11 Edited on 2025-06-17 In Computer Science Views: 42

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

总是在某个位置开始第一次乘法

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$
$Θ ((n - 1)!)$

BF2

必然在某个位置k相乘
BF1“总是在某个位置开始第一次乘法”，子问题规模下降过慢

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) = 2 W (n - 1) + n$
$O (2^{n})$

A DP solution

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]

时间 $Θ (n^{3})$
空间 $Θ (n^{2})$

Weighted Binary Search Tree

规定 $A (T) = \sum_{i = 1}^{n} p_{i} c_{i}$ , 其中 $c_{i} = d e p t h (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_{l o w} + p_{l o w + 1} + \dots + p_{h i g h}$ 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_{l o w}, \dots, K_{h i g h}$ , 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 (l o w, h i g h)$
  - $p (l o w, h i g h)$ 是子问题并入大问题时所付出的代价（修正量）,即 “whole tree”变成子树所付出的修正量
  - $\sum_{i = 1}^{n} (p_{i} . (c_{i} + 1)) = \sum_{i = 1}^{n} p_{i} c_{i} + \sum_{i = 1}^{n} p_{i} = W + p (l o w, h i g h)$
- 根 $K_{r}$ 的代价是 $p_{r}$
So， the recursive relations are:

$A (l o w, h i g h, r) = p_{r} + p (l o w, r - 1) + A (l o w, r - 1) + p (r + 1, h i g h) + A (r + 1, h i g h) = p (l o w, h i g h) + A (l o w, r - 1) + A (r + 1, h i g h)$
- $A (l o w, h i g h) = m i n A (l o w, h i g h, r) | l o w \leq r \leq h i g h$

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;

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

$Θ (n^{3})$

From the DP perspective

All-pairs shortest paths SSSP over DAG

$D . d i s = m i n {B . d i s + 1, C . d i s + 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) = m a x (p_{j} + P (p r e v [j]), P (j - 1))$

One dimension DP algorithm
- Fill in P[0],P[1], ... , P[n]

(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

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 $Θ (W n)$
- The loop is executed at most W/2 times. //每个单词后都有空格,标点
- In fact, W, the line width, is usually a constant. So, $Θ (n)$
- The extra space for the dictionary is $Θ (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] = m i n {c [i - 1, j], 1 + c [1 + c [i, j - d_{i}]}$

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