Download DOC, SLIDE, PPTX
RMC(p,i,j){if i=j thenreturn 0m[i,j]←∞for k←ito j−1 doq←RMC(p,i,k)+RMC(p,k+1,j)+pi−1pkpjif q<m[i,j] thenm[i,j]←qreturn m[i,j] }\begin{align*} & \text{RMC}(p, i, j) \{ \\[5 pt] & \quad \text{if} \ i = j \ \text{then} \\ & \qquad \text{return} \ 0 \\[5 pt] & \quad m[i, j] \leftarrow \infty \\[5 pt] & \quad \text{for} \ k \leftarrow i \text{to} \ j - 1 \ \text{do} \\ & \qquad q \leftarrow \text{RMC}(p, i, k) + \text{RMC}(p, k+1, j) + p_{i-1} p_k p_j \\[5 pt] & \quad if \ q < m[i, j] \ \text{then} \\ & \qquad m[i, j] \leftarrow q \\[5 pt] & \quad \text{return} \ m[i, j] \ \} \end{align*} RMC(p,i,j){if i=j thenreturn 0m[i,j]←∞for k←ito j−1 doq←RMC(p,i,k)+RMC(p,k+1,j)+pi−1pkpjif q<m[i,j] thenm[i,j]←qreturn m[i,j] }
T(1)≥1T(1) \geq 1T(1)≥1 T(n)≥1+∑k=1n−1(T(k)+T(n−k)+1) for n>1T(n) \geq 1 + \sum \limits_{k=1}^{n-1} (T(k)+T(n-k)+1)\ \text{for} \ n>1T(n)≥1+k=1∑n−1(T(k)+T(n−k)+1) for n>1
T(n)≥2∑i=1n−1T(i)+n\begin{align*} T(n) \geq 2 \sum \limits_{i=1}^{n-1}T(i)+n \end{align*} T(n)≥2i=1∑n−1T(i)+n
T(i)≥2i−1 for all i=1,2,…,n−1 and n≥2T(n)≥2∑i=1n−12i−1+n=2∑i=1n−12i−1+n=2(2n−1−1)+n=2n−1+(2n−1−2+n)⇒T(n)≥2n−1 Q.E.D.\begin{align*} T(i) & \geq 2^{i-1} \ \text{for all} \ i=1, 2, \dots, n-1 \ \text{and} \ n \geq 2 \\ T(n) & \geq 2 \sum \limits_{i=1}^{n-1}2^{i-1} + n \\[15 pt] & = 2 \sum \limits_{i=1}^{n-1} 2^{i-1} + n \\ & = 2(2^{n-1}-1) + n \\ & = 2^{n-1} + (2^{n-1} - 2 + n) \\ & \Rightarrow T(n) \geq 2^{n-1} \ \text{ Q.E.D.} \end{align*} T(i)T(n)≥2i−1 for all i=1,2,…,n−1 and n≥2≥2i=1∑n−12i−1+n=2i=1∑n−12i−1+n=2(2n−1−1)+n=2n−1+(2n−1−2+n)⇒T(n)≥2n−1 Q.E.D.
MemoizedMatrixChain(p)n←length[p]−1for i←1 to n dofor j←1 to n dom[i,j]←∞return LookupC(p,1,n)⟹⟹LookupC(p,i,j)if m[i,j]=∞ thenif i=j thenm[i,j]←0elsefor k←i to j−1 doq←LookupC(p,i,k)+LookupC(p,k+1,j)+pi−1pkpjif q<m[i,j] thenm[i,j]←qreturn m[i,j]\begin{align*} \begin{aligned} & \text{MemoizedMatrixChain(p)} \\ & \quad n \leftarrow length[p] - 1 \\ & \quad \text{for} \ i \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad \text{for} \ j \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad \quad m[i, j] \leftarrow \infty \\ & \quad \text{return} \ \text{LookupC}(p, 1, n) \Longrightarrow \end{aligned} \begin{aligned} & \Longrightarrow \text{LookupC}(p, i, j) \\ & \quad \text{if} \ m[i, j] = \infty \ \text{then} \\ & \qquad \text{if} \ i = j \ \text{then} \\ & \qquad \quad m[i, j] \leftarrow 0 \\ & \qquad \text{else} \\ & \qquad \quad \text{for} \ k \leftarrow i \ \text{to} \ j-1 \ \text{do} \\ & \qquad \quad \quad q \leftarrow \text{LookupC}(p, i, k) + \text{LookupC}(p, k+1, j) + p_{i-1} p_k p_j \\ & \qquad \quad \quad \text{if} \ q < m[i, j] \ \text{then} \\ & \qquad \quad \quad \quad m[i, j] \leftarrow q \\ & \quad \text{return} \ m[i, j] \end{aligned} \end{align*} MemoizedMatrixChain(p)n←length[p]−1for i←1 to n dofor j←1 to n dom[i,j]←∞return LookupC(p,1,n)⟹⟹LookupC(p,i,j)if m[i,j]=∞ thenif i=j thenm[i,j]←0elsefor k←i to j−1 doq←LookupC(p,i,k)+LookupC(p,k+1,j)+pi−1pkpjif q<m[i,j] thenm[i,j]←qreturn m[i,j]
Definitions
A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out
Example:
Formal definition: Given a sequence X=⟨x1,x2,…,xm⟩X = \langle x_1, x_2, \dots , x_m \rangleX=⟨x1,x2,…,xm⟩, sequence Z=⟨z1,z2,…,zk⟩Z = \langle z_1, z_2, \dots, z_k \rangleZ=⟨z1,z2,…,zk⟩ is a subsequence of XXX
Example: Z=⟨B,C,D,B⟩Z = \langle B,C,D,B \rangleZ=⟨B,C,D,B⟩ is a subsequence of X=⟨A,B,C,B,D,A,B⟩X = \langle A,B,C,B,D,A,B \rangleX=⟨A,B,C,B,D,A,B⟩ with the index sequence ⟨i1,i2,i3,i4⟩=⟨2,3,5,7⟩\langle i_1, i_2, i_3, i_4 \rangle = \langle 2, 3, 5, 7 \rangle⟨i1,i2,i3,i4⟩=⟨2,3,5,7⟩
If ZZZ is a subsequence of both XXX and YYY, we denote ZZZ as a common subsequence of XXX and YYY.
X=⟨A,B∗,C∗,B,D,A∗,B⟩Y=⟨B∗,D,C∗,A∗,B,A⟩\begin{align*} X &= \langle A,B^*,C^*,B,D,A^*,B \rangle \\ Y &= \langle B^*,D,C^*,A^*,B,A \rangle \end{align*} XY=⟨A,B∗,C∗,B,D,A∗,B⟩=⟨B∗,D,C∗,A∗,B,A⟩
X=⟨A,B,C,B,D,A,B⟩X4=⟨A,B,C,B⟩X0=⟨⟩\begin{align*} X &= \langle A, B, C, B, D, A, B \rangle \\[10 pt] X_4 &= \langle A, B, C, B \rangle \\ X_0 &= \langle \rangle \end{align*} XX4X0=⟨A,B,C,B,D,A,B⟩=⟨A,B,C,B⟩=⟨⟩
LCS(X,Y) {m←length[X]n←length[Y]if xm=yn thenZ←LCS(Xm−1,Yn−1)▹solve one subproblemreturn ⟨Z,xm=yn⟩▹append xm=yn to ZelseZ′←LCS(Xm−1,Y)▹solve two subproblemsZ′′←LCS(X,Yn−1)return longer of Z′ and Z′′}\begin{align*} & \text{LCS}(X, Y) \ \{ \\ & \quad m \leftarrow length[X] \\ & \quad n \leftarrow length[Y] \\ & \quad \text{if} \ x_m = y_n \ \text{then} \\ & \qquad Z \leftarrow \text{LCS}(X_{m-1}, Y_{n-1}) \triangleright \text{solve one subproblem} \\ & \qquad \text{return} \ \langle Z, x_m = y_n \rangle \triangleright \text{append} \ x_m = y_n \ \text{to} \ Z \\ & \quad else \\ & \qquad Z^{'} \leftarrow \text{LCS}(X_{m-1}, Y) \triangleright \text{solve two subproblems} \\ & \qquad Z^{''} \leftarrow \text{LCS}(X, Y_{n-1}) \\ & \qquad \text{return longer of} \ Z^{'} \ \text{and} \ Z^{''} \\ & \} \end{align*} LCS(X,Y) {m←length[X]n←length[Y]if xm=yn thenZ←LCS(Xm−1,Yn−1)▹solve one subproblemreturn ⟨Z,xm=yn⟩▹append xm=yn to ZelseZ′←LCS(Xm−1,Y)▹solve two subproblemsZ′′←LCS(X,Yn−1)return longer of Z′ and Z′′}
c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi=yjmax{c[i,j−1],c[i−1,j]}if i,j>0 and xi≠yj\begin{align*} c[i,j] = \begin{cases} & 0 & \text{if}& \ i=0 \ \text{or} \ j=0 \\ & c[i-1,j-1]+1 & \text{if}& \ i,j>0 \ \text{and} \ x_i=y_j \\ & \text{max}\{c[i,j-1],c[i-1,j]\} & \text{if}& \ i,j>0 \ \text{and} \ x_i \neq y_j \\ \end{cases} \end{align*} c[i,j]=⎩⎨⎧0c[i−1,j−1]+1max{c[i,j−1],c[i−1,j]}ififif i=0 or j=0 i,j>0 and xi=yj i,j>0 and xi=yj
Need to process: c[i,j]c[i, j]c[i,j] after computing: c[i−1,j−1]c[i-1, j-1]c[i−1,j−1], c[i,j−1]c[i, j-1]c[i,j−1], c[i−1,j]c[i-1,j]c[i−1,j]
⇓\Downarrow ⇓
for i←1 to mfor j←1 to n……c[i,j]=⋯\begin{align*} & \text{for} \ i \leftarrow 1 \ \text{to} \ m \\ & \quad \text{for} \ j \leftarrow 1 \ \text{to} \ n \\ & \qquad \dots \\ & \qquad \dots \\ & \qquad c[i, j] = \cdots \end{align*} for i←1 to mfor j←1 to n……c[i,j]=⋯
Total Runtime=Θ(mn)Total Space=Θ(mn){LCS−LENGTH(X,Y)m←length[X];n←length[Y]for i←0 to m do c[i,0]←0for j←0 to n do c[0,j]←0for i←1 to m dofor j←1 to n doif xi=yj thenc[i,j]←c[i−1,j−1]+1b[i,j]←"↖"else if c[i−1,j]≥c[i,j−1]c[i,j]←c[i−1,j]b[i,j]←"↑"elsec[i,j]←c[i,j−1]b[i,j]←"←"\begin{align*} \frac{\text{Total Runtime} = \Theta(mn)}{\text{Total Space} = \Theta(mn)} \begin{cases} & LCS-LENGTH(X,Y) \\ & \quad m \leftarrow length[X]; n \leftarrow length[Y] \\ & \quad \text{for} \ i \leftarrow 0 \ \text{to} \ m \ \text{do} \ c[i, 0] \leftarrow 0 \\ & \quad \text{for} \ j \leftarrow 0 \ \text{to} \ n \ \text{do} \ c[0, j] \leftarrow 0 \\ & \quad \text{for} \ i \leftarrow 1 \ \text{to} \ m \ \text{do} \\ & \qquad \text{for} \ j \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad \quad \text{if} \ x_i = y_j \ \text{then} \\ & \qquad \quad \quad c[i, j] \leftarrow c[i-1, j-1]+1 \\ & \qquad \quad \quad b[i, j] \leftarrow " \nwarrow " \\ & \qquad \quad \text{else if} \ c[i - 1, j] \geq c[i, j-1] \\ & \qquad \quad \quad c[i, j] \leftarrow c[i-1, j] \\ & \qquad \quad \quad b[i, j] \leftarrow "\uparrow " \\ & \qquad \quad \text{else} \\ & \qquad \quad \quad c[i, j] \leftarrow c[i, j-1] \\ & \qquad \quad \quad b[i, j] \leftarrow " \leftarrow " \\ \end{cases} \end{align*} Total Space=Θ(mn)Total Runtime=Θ(mn)⎩⎨⎧LCS−LENGTH(X,Y)m←length[X];n←length[Y]for i←0 to m do c[i,0]←0for j←0 to n do c[0,j]←0for i←1 to m dofor j←1 to n doif xi=yj thenc[i,j]←c[i−1,j−1]+1b[i,j]←"↖"else if c[i−1,j]≥c[i,j−1]c[i,j]←c[i−1,j]b[i,j]←"↑"elsec[i,j]←c[i,j−1]b[i,j]←"←"
Operation of LCS-LENGTH on the sequences
X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*} XY=⟨A1,B2,C3,B4,D5,A6,B7⟩=⟨B1,D2,C3,A4,B5,A6⟩
Running-time = O(mn)O(mn)O(mn) since each table entry takes O(1)O(1)O(1) time to compute
LCS of X&Y=⟨B,C,B,A⟩X \& Y = \langle B, C, B, A \rangleX&Y=⟨B,C,B,A⟩
PRINT-LCS(b,X,i,j)if i=0 orj=0 thenreturnif b[i,j]="↖" thenPRINT-LCS(b,X,i−1,j−1)print xielse if b[i,j]="↑" thenPRINT-LCS(b,X,i−1,j)elsePRINT-LCS(b,X,i,j−1)\begin{align*} & \text{PRINT-LCS}(b, X, i, j) \\ & \quad \text{if} \ i = 0 \ \text{or} j = 0 \ \text{then} \\ & \quad \text{return} \\ & \quad \text{if} \ b[i, j] = " \nwarrow " \ \text{then} \\ & \qquad \text{PRINT-LCS}(b, X, i-1, j-1) \\ & \qquad \text{print} \ x_i \\ & \quad \text{else if} \ b[i, j] = " \uparrow " \ \text{then} \\ & \qquad \text{PRINT-LCS}(b, X, i-1, j) \\ & \quad \text{else} \\ & \qquad \text{PRINT-LCS}(b, X, i, j-1) \end{align*} PRINT-LCS(b,X,i,j)if i=0 orj=0 thenreturnif b[i,j]="↖" thenPRINT-LCS(b,X,i−1,j−1)print xielse if b[i,j]="↑" thenPRINT-LCS(b,X,i−1,j)elsePRINT-LCS(b,X,i,j−1)
To compute c[i,j]c[i, j]c[i,j], we only need c[i−1,j−1]c[i-1, j-1]c[i−1,j−1], c[i−1,j]c[i-1, j]c[i−1,j], and c[i−1,j−1]c[i-1, j-1]c[i−1,j−1]
So, we can store only the last two rows.
This reduces space complexity from Θ(mn)\Theta(mn)Θ(mn) to Θ(n)\Theta(n)Θ(n).
Is there a problem with this approach?
Suppose we know the frequency of each keyword in texts:
begin‾5%,do‾40%,else‾8%,end‾4%,if‾10%,then‾10%,while‾23%,\underset{5\%}{\underline{begin}}, \underset{40\%}{\underline{do}}, \underset{8\%}{\underline{else}}, \underset{4\%}{\underline{end}}, \underset{10\%}{\underline{if}}, \underset{10\%}{\underline{then}}, \underset{23\%}{\underline{while}}, 5%begin,40%do,8%else,4%end,10%if,10%then,23%while,
Example: If we search for keyword "while", we need to access 333 nodes. So, 2323%23 of the queries will have cost of 333.
Total Cost=∑i(depth(i)+1)freq(i)=1×0.04+2×0.4+2×0.1+3×0.05+3×0.08+3×0.1+3×0.23=2.42\begin{align*} \text{Total Cost} &= \sum \limits_{i}^{}(\text{depth}(i)+1)\text{freq}(i) \\ &= 1 \times 0.04 + 2 \times 0.4 + \\ & 2 \times 0.1 + 3 \times 0.05 + \\ & 3 \times 0.08 + 3 \times 0.1 + \\ & 3 \times 0.23 \\ &= 2.42 \end{align*} Total Cost=i∑(depth(i)+1)freq(i)=1×0.04+2×0.4+2×0.1+3×0.05+3×0.08+3×0.1+3×0.23=2.42
Total Cost=∑i(depth(i)+1)freq(i)=1×0.4+2×0.05+2×0.23+3×0.1+4×0.08+4×0.1+5×0.04=2.18\begin{align*} \text{Total Cost} &= \sum \limits_{i}^{}(\text{depth}(i)+1)\text{freq}(i) \\ &= 1 \times 0.4 + 2 \times 0.05 + 2 \times 0.23 + \\ & 3 \times 0.1 + 4 \times 0.08 + \\ & 4 \times 0.1 + 5 \times 0.04 \\ &= 2.18 \end{align*} Total Cost=i∑(depth(i)+1)freq(i)=1×0.4+2×0.05+2×0.23+3×0.1+4×0.08+4×0.1+5×0.04=2.18
Total Cost=∑i(depth(i)+1)freq(i)\begin{align*} \text{Total Cost} &= \sum \limits_{i}^{}(\text{depth}(i)+1)\text{freq}(i) \end{align*} Total Cost=i∑(depth(i)+1)freq(i)
cost(Tij)=cost(TL)+cost(TR)+∑h=ijph\begin{align*} \text{cost}(T_{ij})=\text{cost}(T_{L})+\text{cost}(T_{R})+\sum \limits_{h=i}^{j}p_h \end{align*} cost(Tij)=cost(TL)+cost(TR)+h=i∑jph
Intuition: When we add the root node, the depth of each node in TLT_LTL and TRT_RTR increases by 111. So, the cost of node hhh increases by php_hph. In addition, the cost of root node rrr is prp_rpr. That’s why, we have the last term at the end of the formula above.
cost(Tij)=cost(Ti,m−1)+cost(Tm+1,j)+∑h=ijph\begin{align*} \text{cost}(T_{ij})=\text{cost}(T_{i,m-1})+\text{cost}(T_{m+1,j})+\sum \limits_{h=i}^{j}p_h \end{align*} cost(Tij)=cost(Ti,m−1)+cost(Tm+1,j)+h=i∑jph
Note: We don’t know which root vertex leads to the minimum total cost. So, we need to try each vertex mmm, and choose the one with minimum total cost.
c[i,j]c[i, j]c[i,j]: cost of an optimal BST TijT_{ij}Tij for the subproblem Ki<⋯<KjK_i < \dots < K_jKi<⋯<Kj
c[i,j]={0if i>jmini≤r≤j{c[i,r−1]+c[r+1,j]+Pij}otherwisewhere Pij=∑h=ijph\begin{align*} & c[i,j] = \begin{cases} & 0 & \text{if} \ i>j \\ & \underset{i \leq r \leq j}{\text{min}}\{ c[i,r-1]+c[r+1,j]+P_{ij} \} & \text{otherwise} \\ \end{cases} \\ & \text{where} \ P_{ij}= \sum \limits_{h=i}^{j}p_h \end{align*} c[i,j]={0i≤r≤jmin{c[i,r−1]+c[r+1,j]+Pij}if i>jotherwisewhere Pij=h=i∑jph
c[i,j]={0if i>jmini≤r≤j{c[i,r−1]+c[r+1,j]+Pij}otherwise\begin{align*} & c[i,j] = \begin{cases} & 0 & \text{if} \ i>j \\ & \underset{i \leq r \leq j}{\text{min}}\{ c[i,r-1]+c[r+1,j]+P_{ij} \} & \text{otherwise} \\ \end{cases} \end{align*} c[i,j]={0i≤r≤jmin{c[i,r−1]+c[r+1,j]+Pij}if i>jotherwise
OPTIMAL-BST-COST(p,n)for i←1 to n doc[i,i−1]←0c[i,i]←p[i]R[i,j]←iPS[1]←p[1]⟸PS[i]→ prefix-sum (i):Sum of all p[j] values for j≤ifor i←2 to n doPS[i]←p[i]+PS[i−1]⟸compute the prefix sumfor d←1 to n−1 do⟸BSTs with d+1 consecutive keysfor i←1 to n–d doj←i+dc[i,j]←∞for r←i to j doq←min{c[i,r−1]+c[r+1,j]}+PS[j]–PS[i−1]}if q<c[i,j] thenc[i,j]←qR[i,j]←rreturn c[1,n],R\begin{align*} & \text{OPTIMAL-BST-COST} (p, n) \\ & \quad \text{for} \ i \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad c[i, i-1] \leftarrow 0 \\ & \qquad c[i, i] \leftarrow p[i] \\ & \qquad R[i, j] \leftarrow i \\ & \quad PS[1] \leftarrow p[1] \Longleftarrow PS[i] \rightarrow \text{ prefix-sum } (i): \text{Sum of all} \ p[j] \ \text{values for} \ j \leq i \\ & \quad \text{for} \ i \leftarrow 2 \ \text{to} \ n \ \text{do} \\ & \qquad PS[i] \leftarrow p[i] + PS[i-1] \Longleftarrow \text{compute the prefix sum} \\ & \quad \text{for} \ d \leftarrow 1 \ \text{to} \ n−1 \ \text{do} \Longleftarrow \text{BSTs with} \ d+1 \ \text{consecutive keys} \\ & \qquad \text{for} \ i \leftarrow 1 \ \text{to} \ n – d \ \text{do} \\ & \qquad \quad j \leftarrow i + d \\ & \qquad \quad c[i, j] \leftarrow \infty \\ & \qquad \quad \text{for} \ r \leftarrow i \ \text{to} \ j \ \text{do} \\ & \qquad \qquad q \leftarrow min\{c[i,r-1] + c[r+1, j]\} + PS[j] – PS[i-1]\} \\ & \qquad \qquad \text{if} \ q < c[i, j] \ \text{then} \\ & \qquad \qquad \quad c[i, j] \leftarrow q \\ & \qquad \qquad \quad R[i, j] \leftarrow r \\ & \quad \text{return} \ c[1, n], R \end{align*} OPTIMAL-BST-COST(p,n)for i←1 to n doc[i,i−1]←0c[i,i]←p[i]R[i,j]←iPS[1]←p[1]⟸PS[i]→ prefix-sum (i):Sum of all p[j] values for j≤ifor i←2 to n doPS[i]←p[i]+PS[i−1]⟸compute the prefix sumfor d←1 to n−1 do⟸BSTs with d+1 consecutive keysfor i←1 to n–d doj←i+dc[i,j]←∞for r←i to j doq←min{c[i,r−1]+c[r+1,j]}+PS[j]–PS[i−1]}if q<c[i,j] thenc[i,j]←qR[i,j]←rreturn c[1,n],R
Pij=∑h=ijph\begin{align*} P_{ij} = \sum \limits_{h=i}^{j}p_h \end{align*} Pij=h=i∑jph
If we compute the summation directly for every (i,j)(i, j)(i,j) pair, the runtime would be Θ(n3)\Theta(n^3)Θ(n3).
Instead, we spend O(n)O(n)O(n) time in preprocessing to compute the prefix sum array PS. Then we can compute each PijP_{ij}Pij in O(1)O(1)O(1) time using PS.
p:0.051 0.022 0.063 0.074 0.205 0.056 0.087 0.028PS:0.051 0.072 0.133 0.204 0.405 0.456 0.537 0.558P27=PS[7]–PS[1]=0.53–0.05=0.48P36=PS[6]–PS[2]=0.45–0.07=0.38\begin{align*} p &: \overset{1}{0.05} \ \overset{2}{0.02} \ \overset{3}{0.06} \ \overset{4}{0.07} \ \overset{5}{0.20} \ \overset{6}{0.05} \ \overset{7}{0.08} \ \overset{8}{0.02} \\ PS &: \overset{1}{0.05} \ \overset{2}{0.07} \ \overset{3}{0.13} \ \overset{4}{0.20} \ \overset{5}{0.40} \ \overset{6}{0.45} \ \overset{7}{0.53} \ \overset{8}{0.55} \\[10 pt] P_{27} &= PS[7] – PS[1] = 0.53 – 0.05 = 0.48 \\ P_{36} &= PS[6] – PS[2] = 0.45 – 0.07 = 0.38 \end{align*} pPSP27P36:0.051 0.022 0.063 0.074 0.205 0.056 0.087 0.028:0.051 0.072 0.133 0.204 0.405 0.456 0.537 0.558=PS[7]–PS[1]=0.53–0.05=0.48=PS[6]–PS[2]=0.45–0.07=0.38
Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.
Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming.
#include <stdio.h> // a simple recursive program to compute fibonacci numbers int fib(int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); } int main() { int n = 5; printf("Fibonacci number is %d ", fib(n)); return 0; }
Output
Fibonacci number is 5
/* a simple recursive program for Fibonacci numbers */ public class Fibonacci { public static void main(String[] args) { int n = Integer.parseInt(args[0]); System.out.println(fib(n)); } public static int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } }
public class Fibonacci { public static void Main(string[] args) { int n = int.Parse(args[0]); Console.WriteLine(fib(n)); } public static int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } }
fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0)
fib(3)
There are following two different ways to store the values so that these values can be reused:
NIL
/* C++ program for Memoized version for nth Fibonacci number */ #include <bits/stdc++.h> using namespace std; #define NIL -1 #define MAX 100 int lookup[MAX];
/* Function to initialize NIL values in lookup table */ void _initialize() { int i; for (i = 0; i < MAX; i++) lookup[i] = NIL; }
/* function for nth Fibonacci number */ int fib(int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n - 1) + fib(n - 2); } return lookup[n]; }
// Driver code int main() { int n = 40; _initialize(); cout << "Fibonacci number is " << fib(n); return 0; }
/* Java program for Memoized version */ public class Fibonacci { final int MAX = 100; final int NIL = -1; int lookup[] = new int[MAX]; /* Function to initialize NIL values in lookup table */ void _initialize() { for (int i = 0; i < MAX; i++) lookup[i] = NIL; }
public static void main(String[] args) { Fibonacci f = new Fibonacci(); int n = 40; f._initialize(); System.out.println("Fibonacci number is" + " " + f.fib(n)); } }
// C# program for Memoized versionof nth Fibonacci number using System; class FiboCalcMemoized { static int MAX = 100; static int NIL = -1; static int[] lookup = new int[MAX]; /* Function to initialize NIL values in lookup table */ static void initialize() { for (int i = 0; i < MAX; i++) lookup[i] = NIL; }
/* function for nth Fibonacci number */ static int fib(int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n - 1) + fib(n - 2); } return lookup[n]; }
// Driver code public static void Main() { int n = 40; initialize(); Console.Write("Fibonacci number is" + " " + fib(n)); } }
fib(0)
fib(1)
fib(2)
/* C program for Tabulated version */ #include <stdio.h> int fib(int n) { int f[n + 1]; int i; f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; return f[n]; }
... int main() { int n = 9; printf("Fibonacci number is %d ", fib(n)); return 0; }
Output:
Fibonacci number is 34
/* Java program for Tabulated version */ public class Fibonacci { public static void main(String[] args) { int n = 9; System.out.println("Fibonacci number is " + fib(n)); }
/* Function to calculate nth Fibonacci number */ static int fib(int n) { int f[] = new int[n + 1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; return f[n]; } }
// C# program for Tabulated version using System; class Fibonacci { static int fib(int n) { int[] f = new int[n + 1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; return f[n]; } public static void Main() { int n = 9; Console.Write("Fibonacci number is" + " " + fib(n)); } }
To see the optimization achieved by Memoized and Tabulated solutions over the basic Recursive solution, see the time taken by following runs for calculating the 40th Fibonacci number:
Recursive Solution:
Memoized Solution:
Tabulated Solution:
A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.
For example, the Shortest Path problem has following optimal substructure property:
https://www.coursera.org/learn/dna-sequencing
Introduction to Algorithms, Third Edition | The MIT Press
Bilkent CS473 Course Notes (new)
Bilkent CS473 Course Notes (old)
−End−Of−Week−6−Course−Module−-End-Of-Week-6-Course-Module-−End−Of−Week−6−Course−Module−
- Memoization-based solutions will NOT BE ACCEPTED in the exams!