: Not a specific algorithm, but a design paradigm(strategy)
- Used for optimization(making choice) problems:
– Find a solution with the optimal value
– Minimization or maximization
Ex_ Shortest-path, Job scheduling
- S = combine( S1, S2, ..., Sm ) ➡️ smaller problem
- D and C와 비슷하지만 bottom-up fashion
![](https://velog.velcdn.com/images/choihjin/post/da914c9a-0850-4386-ba42-bf24a6fbef32/image.png)
Divide and Conquer vs. DP
A divide-and-conquer algorithm may do more work than necessary, repeatedly solving the common subproblems. A dynamic-programming algorithm solves every subproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subproblem is encountered. Dynamic programming is typically applied to optimization problems.
Matrix Multiplication
parenthesizing
- Given a p × q matrix A and a q × r matrix B, their product is a p × r matrix C defined by
![](https://velog.velcdn.com/images/choihjin/post/8a4e2f25-613f-4545-92fb-ddf18b850dcc/image.png)
- The cost of computing C is p · q · r
- Given three matrices:
A = p × q matrix
B = q × r matrix
C = r × s matrix
- Two ways : ( A · B ) · C or A · ( B · C )
- first p · q · r + p · r · s = p · r · ( q + s )
- second q · r · s + p · q · s = ( p + r ) · q · s
- The ways of parenthesizing make a rather dramatic difference
Ex_![](https://velog.velcdn.com/images/choihjin/post/0cc9e8b3-305d-4222-a393-bf3d91a3caa3/image.png)
![](https://velog.velcdn.com/images/choihjin/post/4c2553d9-b6ef-45b5-8667-9b1c8be864db/image.png)
➡️ brute-forece로 어떻게 곱하는지는 의미가 없다. 답은 DP
왜 이렇게 오래걸릴까? Recalculation!!![](https://velog.velcdn.com/images/choihjin/post/9bc91fee-a13b-49cd-883c-f1b02f5e2447/image.png)
Structure of Optimal Solution
- Key Observation : Given optimal sequence Ai Ai+1 .... Aj, suppose the sequence is split between Ak and Ak+1. Then the sequence Ai ... Ak, and Ak+1 ... Aj are optimal ➡️ (Ai ... Ak), (Ak+1 ... Aj) 각각 optimal
![](https://velog.velcdn.com/images/choihjin/post/80a56843-cea5-42d6-b183-248ce6a206c9/image.png)
- Optimal Substructure: An optimal solution to an instance contains within it optimal solutions to smaller instances of the same problem.
- Optimal Overlapping Subproblems: A recursive solution to the problem solves certain smaller instances of the same problem over and over again, rather than new subproblems.
- Principle of Optimality
- Given an optimization problem and an associated function combine, the Principle of Optimality holds if the following is always true:
➡️ Optimal Substruct.가 있을 때![](https://velog.velcdn.com/images/choihjin/post/d7380b26-4f6f-43ca-ab7e-ecad0e17fa18/image.png)
Memoization
: DP approach while maintaing top-down strategy ➡️ Avoiding recaculation
➡️ 둘다 θ(n)
Optimal Substructure in MCM![](https://velog.velcdn.com/images/choihjin/post/10e9be67-0902-4246-9370-f8f03a07cbe0/image.png)
- Development of DP algorithms
- Characterize the structure of an optimal solution
- Recursively define(relation , represent to expression) the value of an optimal solution
- Compute the value of an optimal solution in a bottom-up fashion
- Construct(구성) an optimal solution from computed information
Step 1
- Find the optimal substructure
: From the key observation we identified optimal substructure.
- We can build an optimal solution to an instance of the matrix-chain multiplication problem by splitting the problem into two subproblems (optimally parenthesizing AiAi+1Ak and Ak+1Ak+2Aj), finding optimal solutions to subproblem instances, and then combining these optimal subproblem solutions..
Step 2: A recursive solution
- m[i,j]: the minimum number of scalar multiplications needed to compute Ai ...Aj
- final solution: m[1,n]
- Recursively,
- if i=j, m[i,j]=0 (trivial)
- if i<j, m[i,j]=m[i,k]+m[k+1,j]+pi−1pkpj for some k
Size of matrix Ai = pi−1pi
![](https://velog.velcdn.com/images/choihjin/post/bd8d05e7-9012-4c41-9989-71d199fc5645/image.png)
- s[i,j]: a value k
![](https://velog.velcdn.com/images/choihjin/post/8ef4fb03-c976-4867-8505-12b8d168ce36/image.png)
Step 3: Computing the optimal costs![](https://velog.velcdn.com/images/choihjin/post/3293bb56-52d5-44f3-90c9-455575f595ee/image.png)
![](https://velog.velcdn.com/images/choihjin/post/850575a5-9500-4f23-bfed-8583fd03e177/image.png)
![](https://velog.velcdn.com/images/choihjin/post/0b3caaa3-1de9-40fb-aee2-8ea10b6cefd1/image.png)
![](https://velog.velcdn.com/images/choihjin/post/93d9e1a7-3163-4073-a787-c805b47bc87d/image.png)
Step 4 : Constructing an optimal solution![](https://velog.velcdn.com/images/choihjin/post/c8cd2c73-9067-48c0-bd76-d7de8cf861fa/image.png)
Exercise![](https://velog.velcdn.com/images/choihjin/post/f9519dd2-c458-48ab-ab40-075cf5e6b880/image.png)
Exercise in class
1. T / F
Dynamic Programming is typically applied to opimization problem
➡️ T
2. DP vs. D and C
(a) How to alike?
➡️ subproblem으로 쪼개서 푸는것
(b) What is the difference?
➡️ top-down, bottom-up
(c) Which require more work?
➡️ D and C
3. What does opimal substructure mean?
➡️ An optimal solution to an instance contains within it optimal solutions to smaller instances of the same problem.
4. What does overlapping subproblem mean?
➡️ A recursive solution to the problem solves certain smaller instances of the same problem over and over again, rather than new subproblems.
5. MCM Problem
matrix | dimesion |
---|
A1 | 30 x 35 |
A2 | 35 x 15 |
A3 | 15 x 5 |
A4 | 5 x 10 |
A5 | 10 x 20 |
A6 | 20 x 25 |
![](https://velog.velcdn.com/images/choihjin/post/b2d3b55f-91fe-497d-b9a7-d9da477713c7/image.png)
![](https://velog.velcdn.com/images/choihjin/post/81bba157-d7b8-44e1-8e66-ca9d4c54dea2/image.png)
HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.