DSA Part 8: Dynamic Programming
Post
Cancel

# DSA Part 8: Dynamic Programming

Dynamic Programming is an optimization over plain recursion. In this, we re-use the solutions of subproblems for overlapping subproblems

Two types are

1. Memoization - Top Down

No of dimenstions $rightarrow$ No of changing params in the recursive call. Will reduce the time complexity from $O(2^n)$ to $O(n)$.

1 2 3 4 5 6 7 8 9 10 int memo[n+1]; memset(memo, -1, sizeof(memo)); int fib(int n){ if(memo[n] == -1) memo[n] == (n == 0 || n==1) ? n : fib(n-1) + fib(n-2); return memo[n]; } 

2. Tabulation - Bottom Up

Doesn’t consume space in stack for recursion calls.

1 2 3 4 5 6 7 8 9 10 11 int fib(int n){ int f[n+1]; f[0] = 0, f[1] = 1; for(int i=2; i<=n; i++) f[i] = f[i-i] + f[i-2]; return f[n]; } 

## Applications

UtitlityAlgorithm
Git DiffLCS
Close SearchEdit distance
Shortest PathBellman Ford, Floyd Warshall
Resource Allocation0-1 knapsack

## Problem

### Longest Common Subsequences

Given two sequences, find the length of longest subsequence present in both of them.

1 2 3 4 5 6 7 8 9 10 int longestCommonSubstr (string S1, string S2, int n, int m) { if(n == 0 || m == 0) return 0; if(S1[n-1] == S2[m-1]) return 1 + longestCommonSubstr(S1, S2, n-1, m-1); return max(longestCommonSubstr(S1, S2, n, m-1), longestCommonSubstr(S1, S2, n-1, m)); } 

Time Complexity: $O(2^n)$

• Memoization
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int lcs( string s1, string s2, int m, int n, vector<vector<int> >& dp){ if(dp[m][n] != -1) return dp[m][n]; if(m == 0 || n == 0) return 0; if (s1[m-1] == s2[n-1]) return dp[m][n] = 1 + lcs(s1, s2, m-1, n-1); return dp[m][n] = max(lcs(s1, s2, m-1, n), lcs(s1, s2, m, n-1)); } 

Time Complexity: $O(m \times n)$

Auxiliary Space: $O(m \times n)$

• Tabulation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int lcs(int m, int n, string X, string Y) { int L[m+1][n+1]; for (int i=0; i<=m; i++) for (int j=0; j<=n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i-1] == Y[j-1]) L[i][j] = L[i-1][j-1] + 1; else L[i][j] = max(L[i-1][j], L[i][j-1]); } return L[m][n]; } 

Time Complexity: $O(m \times n)$

Auxiliary Space: $O(m \times n)$

• Space Optimized
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int lcs(int m, int n, string X, string Y) { int L[2][n + 1]; bool index; for (int i = 0; i <= m; i++) { index = i & 1; for (int j = 0; j <= n; j++) if (i == 0 || j == 0) L[index][j] = 0; else if (X[i-1] == Y[j-1]) L[index][j] = L[1 - index][j - 1] + 1; else L[index][j] = max(L[1 - index][j], L[index][j - 1]); } return L[index][n]; } 

Time Complexity: $O(m \times n)$

Auxiliary Space: $O(n)$

### Coin Change

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of $S = { S1, S2, .. , SM }$ valued coins.

• Naive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 long long int count(int S[], int m, int n) { long long int i, j,x,y,table[n + 1][m]; for (i = 0; i < m; i++) table[0][i] = 1; for (i = 1; i < n + 1; i++) { for (j = 0; j < m; j++) { x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0; y = (j >= 1) ? table[i][j - 1] : 0; table[i][j] = x + y; } } return table[n][m - 1]; } 
• Optimal