Skip to content

Commit bd2635b

Browse files
s-tutis-tuti
authored
Update dynamic-programming.md
1 parent 7b123e5 commit bd2635b

File tree

1 file changed

+189
-0
lines changed

1 file changed

+189
-0
lines changed

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

Lines changed: 189 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -234,3 +234,192 @@ 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+
# Output: Edit Distance between 'sunday' and 'saturday' is 3.
269+
```
270+
## String Edit Distance Code in Python (Bottom-Up Approach)
271+
```python
272+
def edit_distance(str1, str2):
273+
m, n = len(str1), len(str2)
274+
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
275+
276+
for i in range(m + 1):
277+
for j in range(n + 1):
278+
if i == 0:
279+
dp[i][j] = j
280+
elif j == 0:
281+
dp[i][j] = i
282+
elif str1[i - 1] == str2[j - 1]:
283+
dp[i][j] = dp[i - 1][j - 1]
284+
else:
285+
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
286+
287+
return dp[m][n]
288+
289+
str1 = "sunday"
290+
str2 = "saturday"
291+
print(f"Edit Distance between '{str1}' and '{str2}' is {edit_distance(str1, str2)}.")
292+
# Output: Edit Distance between 'sunday' and 'saturday' is 3.
293+
```
294+
## **Complexity Analysis:**
295+
- **Time Complexity:** O(m * n) where m and n are the lengths of string 1 and string 2 respectively
296+
- **Space Complexity:** O(m * n) for both top-down and bottom-up approaches
297+
298+
299+
# 6. Matrix Chain Multiplication
300+
301+
The Matrix Chain Multiplication finds the optimal way to multiply a sequence of matrices to minimize the number of scalar multiplications.
302+
303+
**Algorithm Overview:**
304+
- **Base Cases:** The cost of multiplying one matrix is zero.
305+
- **Memoization:** Store the results of previously computed matrix chain orders to avoid redundant computations.
306+
- **Recurrence Relation:** Compute the optimal cost by splitting the product at different points and choosing the minimum cost.
307+
308+
## Matrix Chain Multiplication Code in Python (Top-Down Approach with Memoization)
309+
```python
310+
def matrix_chain_order(p, memo={}):
311+
n = len(p) - 1
312+
def compute_cost(i, j):
313+
if (i, j) in memo:
314+
return memo[(i, j)]
315+
if i == j:
316+
return 0
317+
memo[(i, j)] = float('inf')
318+
for k in range(i, j):
319+
q = compute_cost(i, k) + compute_cost(k + 1, j) + p[i - 1] * p[k] * p[j]
320+
if q < memo[(i, j)]:
321+
memo[(i, j)] = q
322+
return memo[(i, j)]
323+
return compute_cost(1, n)
324+
325+
p = [1, 2, 3, 4]
326+
print(f"Minimum number of multiplications is {matrix_chain_order(p)}.")
327+
# Output: Minimum number of multiplications is 18.
328+
```
329+
## Matrix Chain Multiplication Code in Python (Bottom-Up Approach)
330+
```python
331+
def matrix_chain_order(p):
332+
n = len(p) - 1
333+
m = [[0 for _ in range(n)] for _ in range(n)]
334+
335+
for L in range(2, n + 1):
336+
for i in range(n - L + 1):
337+
j = i + L - 1
338+
m[i][j] = float('inf')
339+
for k in range(i, j):
340+
q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
341+
if q < m[i][j]:
342+
m[i][j] = q
343+
344+
return m[0][n - 1]
345+
346+
p = [1, 2, 3, 4]
347+
print(f"Minimum number of multiplications is {matrix_chain_order(p)}.")
348+
# Output: Minimum number of multiplications is 18.
349+
```
350+
## **Complexity Analysis:**
351+
- **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`
352+
- **Space Complexity:** O(n^2) for both top-down and bottom-up approaches
353+
354+
355+
# 7. Optimal Binary Search Tree
356+
357+
The Matrix Chain Multiplication finds the optimal way to multiply a sequence of matrices to minimize the number of scalar multiplications.
358+
359+
**Algorithm Overview:**
360+
- **Base Cases:** The cost of a single key is its frequency.
361+
- **Memoization:** Store the results of previously computed subproblems to avoid redundant computations.
362+
- **Recurrence Relation:** Compute the optimal cost by trying each key as the root and choosing the minimum cost.
363+
364+
## Optimal Binary Search Tree Code in Python (Top-Down Approach with Memoization)
365+
```python
366+
def optimal_bst(keys, freq, memo={}):
367+
n = len(keys)
368+
def compute_cost(i, j):
369+
if (i, j) in memo:
370+
return memo[(i, j)]
371+
if i > j:
372+
return 0
373+
if i == j:
374+
return freq[i]
375+
memo[(i, j)] = float('inf')
376+
total_freq = sum(freq[i:j+1])
377+
for r in range(i, j + 1):
378+
cost = (compute_cost(i, r - 1) +
379+
compute_cost(r + 1, j) +
380+
total_freq)
381+
if cost < memo[(i, j)]:
382+
memo[(i, j)] = cost
383+
return memo[(i, j)]
384+
return compute_cost(0, n - 1)
385+
386+
keys = [10, 12, 20]
387+
freq = [34, 8, 50]
388+
print(f"Cost of Optimal BST is {optimal_bst(keys, freq)}.")
389+
# Output: Cost of Optimal BST is 142.
390+
```
391+
## Optimal Binary Search Tree Code in Python (Bottom-Up Approach)
392+
```python
393+
def optimal_bst(keys, freq):
394+
n = len(keys)
395+
cost = [[0 for x in range(n)] for y in range(n)]
396+
397+
for i in range(n):
398+
cost[i][i] = freq[i]
399+
400+
for L in range(2, n + 1):
401+
for i in range(n - L + 1):
402+
j = i + L - 1
403+
cost[i][j] = float('inf')
404+
total_freq = sum(freq[i:j+1])
405+
for r in range(i, j + 1):
406+
c = (cost[i][r - 1] if r > i else 0) + \
407+
(cost[r + 1][j] if r < j else 0) + \
408+
total_freq
409+
if c < cost[i][j]:
410+
cost[i][j] = c
411+
412+
return cost[0][n - 1]
413+
414+
keys = [10, 12, 20]
415+
freq = [34, 8, 50]
416+
print(f"Cost of Optimal BST is {optimal_bst(keys, freq)}.")
417+
# Output: Cost of Optimal BST is 142.
418+
```
419+
## **Complexity Analysis:**
420+
- **Time Complexity:** O(n^3) where n is the number of keys in the binary search tree.
421+
- **Space Complexity:** O(n^2) for both top-down and bottom-up approaches
422+
423+
</br>
424+
<hr>
425+
</br>

0 commit comments

Comments
 (0)