## Dynamic Programming

- Solves complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.
- Required Properties
- Overlapping Sub problems
- Example of Fibonacci Numbers
- Memorise solution of sub number and store it then if required use that rather calculating again
- Ways to store value
- Memoization (Top – Down)
- First check in memory table to check result else calculate

- Tabulation (Bottom Up)
- Build a table bottom up fashion and return last entry
- Example from fib(0) => fib(1) . . . => fib(n)

- Memoization (Top – Down)
- In Memoized version, table is filled on demand while in Tabulated version, starting from the first entry, all entries are filled one by one.

- Optimal Substructure
- 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
- If a node x between shortest path between Node U & V
- Then short(u,v)=short(u,x)+short(x,v);

### Longest Increasing Subsequence

- Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
- The length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
- Optimal Substructure
- Let arr[0..n-1] be the input array
- L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.
- Then, L(i) can be recursively written as:
- L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
- L(i) = 1, if no such j exists.
- To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
- Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.

- Overlapping solution: lis(4) => lis(3) example
- Time Complexity => O(n2)

### Longest Common Subsequence

- Find the length of longest subsequence present in both of them.
- A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
- For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.

- String of length n has 2^n different possible subsequences.

Advertisements

## Leave a Reply