Dynamic Programming

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)
    • 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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: