Skip to content

Commit 7ce4edc

Browse files
ashitaprasadashitaprasad
authored
Merge pull request animator#1287 from s-tuti/Patch-3
Updated Dynamic Programming Section with More Examples
2 parents 8a32cba + 59e2353 commit 7ce4edc

File tree

1 file changed

+217
-0
lines changed

1 file changed

+217
-0
lines changed

‎contrib/ds-algorithms/dynamic-programming.md

Lines changed: 217 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -234,3 +234,220 @@ print("Length of lis is", lis(arr))
234234
## Complexity Analysis
235235
- **Time Complexity**: O(n * n) for both approaches, where n is the length of the array.
236236
- **Space Complexity**: O(n * n) for the memoization table in Top-Down Approach, O(n) in Bottom-Up Approach.
237+
238+
# 5. String Edit Distance
239+
240+
The String Edit Distance algorithm calculates the minimum number of operations (insertions, deletions, or substitutions) required to convert one string into another.
241+
242+
**Algorithm Overview:**
243+
- **Base Cases:** If one string is empty, the edit distance is the length of the other string.
244+
- **Memoization:** Store the results of previously computed edit distances to avoid redundant computations.
245+
- **Recurrence Relation:** Compute the edit distance by considering insertion, deletion, and substitution operations.
246+
247+
## String Edit Distance Code in Python (Top-Down Approach with Memoization)
248+
```python
249+
def edit_distance(str1, str2, memo={}):
250+
m, n = len(str1), len(str2)
251+
if (m, n) in memo:
252+
return memo[(m, n)]
253+
if m == 0:
254+
return n
255+
if n == 0:
256+
return m
257+
if str1[m - 1] == str2[n - 1]:
258+
memo[(m, n)] = edit_distance(str1[:m-1], str2[:n-1], memo)
259+
else:
260+
memo[(m, n)] = 1 + min(edit_distance(str1, str2[:n-1], memo), # Insert
261+
edit_distance(str1[:m-1], str2, memo), # Remove
262+
edit_distance(str1[:m-1], str2[:n-1], memo)) # Replace
263+
return memo[(m, n)]
264+
265+
str1 = "sunday"
266+
str2 = "saturday"
267+
print(f"Edit Distance between '{str1}' and '{str2}' is {edit_distance(str1, str2)}.")
268+
```
269+
270+
#### Output
271+
```
272+
Edit Distance between 'sunday' and 'saturday' is 3.
273+
```
274+
275+
## String Edit Distance Code in Python (Bottom-Up Approach)
276+
```python
277+
def edit_distance(str1, str2):
278+
m, n = len(str1), len(str2)
279+
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
280+
281+
for i in range(m + 1):
282+
for j in range(n + 1):
283+
if i == 0:
284+
dp[i][j] = j
285+
elif j == 0:
286+
dp[i][j] = i
287+
elif str1[i - 1] == str2[j - 1]:
288+
dp[i][j] = dp[i - 1][j - 1]
289+
else:
290+
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
291+
292+
return dp[m][n]
293+
294+
str1 = "sunday"
295+
str2 = "saturday"
296+
print(f"Edit Distance between '{str1}' and '{str2}' is {edit_distance(str1, str2)}.")
297+
```
298+
299+
#### Output
300+
```
301+
Edit Distance between 'sunday' and 'saturday' is 3.
302+
```
303+
304+
## **Complexity Analysis:**
305+
- **Time Complexity:** O(m * n) where m and n are the lengths of string 1 and string 2 respectively
306+
- **Space Complexity:** O(m * n) for both top-down and bottom-up approaches
307+
308+
309+
# 6. Matrix Chain Multiplication
310+
311+
The Matrix Chain Multiplication finds the optimal way to multiply a sequence of matrices to minimize the number of scalar multiplications.
312+
313+
**Algorithm Overview:**
314+
- **Base Cases:** The cost of multiplying one matrix is zero.
315+
- **Memoization:** Store the results of previously computed matrix chain orders to avoid redundant computations.
316+
- **Recurrence Relation:** Compute the optimal cost by splitting the product at different points and choosing the minimum cost.
317+
318+
## Matrix Chain Multiplication Code in Python (Top-Down Approach with Memoization)
319+
```python
320+
def matrix_chain_order(p, memo={}):
321+
n = len(p) - 1
322+
def compute_cost(i, j):
323+
if (i, j) in memo:
324+
return memo[(i, j)]
325+
if i == j:
326+
return 0
327+
memo[(i, j)] = float('inf')
328+
for k in range(i, j):
329+
q = compute_cost(i, k) + compute_cost(k + 1, j) + p[i - 1] * p[k] * p[j]
330+
if q < memo[(i, j)]:
331+
memo[(i, j)] = q
332+
return memo[(i, j)]
333+
return compute_cost(1, n)
334+
335+
p = [1, 2, 3, 4]
336+
print(f"Minimum number of multiplications is {matrix_chain_order(p)}.")
337+
```
338+
339+
#### Output
340+
```
341+
Minimum number of multiplications is 18.
342+
```
343+
344+
345+
## Matrix Chain Multiplication Code in Python (Bottom-Up Approach)
346+
```python
347+
def matrix_chain_order(p):
348+
n = len(p) - 1
349+
m = [[0 for _ in range(n)] for _ in range(n)]
350+
351+
for L in range(2, n + 1):
352+
for i in range(n - L + 1):
353+
j = i + L - 1
354+
m[i][j] = float('inf')
355+
for k in range(i, j):
356+
q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
357+
if q < m[i][j]:
358+
m[i][j] = q
359+
360+
return m[0][n - 1]
361+
362+
p = [1, 2, 3, 4]
363+
print(f"Minimum number of multiplications is {matrix_chain_order(p)}.")
364+
```
365+
366+
#### Output
367+
```
368+
Minimum number of multiplications is 18.
369+
```
370+
371+
## **Complexity Analysis:**
372+
- **Time Complexity:** O(n^3) where n is the number of matrices in the chain. For an `array p` of dimensions representing the matrices such that the `i-th matrix` has dimensions `p[i-1] x p[i]`, n is `len(p) - 1`
373+
- **Space Complexity:** O(n^2) for both top-down and bottom-up approaches
374+
375+
# 7. Optimal Binary Search Tree
376+
377+
The Matrix Chain Multiplication finds the optimal way to multiply a sequence of matrices to minimize the number of scalar multiplications.
378+
379+
**Algorithm Overview:**
380+
- **Base Cases:** The cost of a single key is its frequency.
381+
- **Memoization:** Store the results of previously computed subproblems to avoid redundant computations.
382+
- **Recurrence Relation:** Compute the optimal cost by trying each key as the root and choosing the minimum cost.
383+
384+
## Optimal Binary Search Tree Code in Python (Top-Down Approach with Memoization)
385+
386+
```python
387+
def optimal_bst(keys, freq, memo={}):
388+
n = len(keys)
389+
def compute_cost(i, j):
390+
if (i, j) in memo:
391+
return memo[(i, j)]
392+
if i > j:
393+
return 0
394+
if i == j:
395+
return freq[i]
396+
memo[(i, j)] = float('inf')
397+
total_freq = sum(freq[i:j+1])
398+
for r in range(i, j + 1):
399+
cost = (compute_cost(i, r - 1) +
400+
compute_cost(r + 1, j) +
401+
total_freq)
402+
if cost < memo[(i, j)]:
403+
memo[(i, j)] = cost
404+
return memo[(i, j)]
405+
return compute_cost(0, n - 1)
406+
407+
keys = [10, 12, 20]
408+
freq = [34, 8, 50]
409+
print(f"Cost of Optimal BST is {optimal_bst(keys, freq)}.")
410+
```
411+
412+
#### Output
413+
```
414+
Cost of Optimal BST is 142.
415+
```
416+
417+
## Optimal Binary Search Tree Code in Python (Bottom-Up Approach)
418+
419+
```python
420+
def optimal_bst(keys, freq):
421+
n = len(keys)
422+
cost = [[0 for x in range(n)] for y in range(n)]
423+
424+
for i in range(n):
425+
cost[i][i] = freq[i]
426+
427+
for L in range(2, n + 1):
428+
for i in range(n - L + 1):
429+
j = i + L - 1
430+
cost[i][j] = float('inf')
431+
total_freq = sum(freq[i:j+1])
432+
for r in range(i, j + 1):
433+
c = (cost[i][r - 1] if r > i else 0) + \
434+
(cost[r + 1][j] if r < j else 0) + \
435+
total_freq
436+
if c < cost[i][j]:
437+
cost[i][j] = c
438+
439+
return cost[0][n - 1]
440+
441+
keys = [10, 12, 20]
442+
freq = [34, 8, 50]
443+
print(f"Cost of Optimal BST is {optimal_bst(keys, freq)}.")
444+
```
445+
446+
#### Output
447+
```
448+
Cost of Optimal BST is 142.
449+
```
450+
451+
### Complexity Analysis
452+
- **Time Complexity**: O(n^3) where n is the number of keys in the binary search tree.
453+
- **Space Complexity**: O(n^2) for both top-down and bottom-up approaches

0 commit comments

Comments
 (0)