Dynamic Programming

1. There are two types of problems, increasing and common type where we assume half the array is solved and how can we add another element to the solution and maintain all the constraints. There is another type like common subsequence or coin change, where we find out the total combinations in the solution possible. There we formulate the problem such that we either take the nth element or we don't take the nth element.
2. Longest Continuous Subarray : maxsoFar = max(maxsoFar + A[I], 0)
1.                      maxEndingHere = max(maxEndingHere, maxSoFar)
3. Longest Increasing Subsequence : I need to figure out how to output the longest increasing subsequence as well. I need to study efficient algorithms for longest increasing subsequence as well which work in O(nlogn) time. /* Initialize LIS values for all indexes */
      for ( i = 0; i < n; i++ )
         lis[i] = 1;
       
      /* Compute optimized LIS values in bottom up manner */
      for ( i = 1; i < n; i++ )
         for ( j = 0; j < i; j++ )
            if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
               lis[i] = lis[j] + 1;
       
      /* Pick maximum of all LIS values */
      for ( i = 0; i < n; i++ )
         if ( max < lis[i] )
            max = lis[i];
    
4. Longest Common Subsequence : I need to study other variants of LCS. I need to study some problems of the kind, given the LCS, how can you solve this problem, using this algorithm. This is a nice variant. If last characters of both sequences match (or X[m-1] == Y[n-1]) then
   L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
   If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
   L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
5. Edit Distance Code
6. http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/ - I solved this in somewhat worse than O(n) and somewhat better than O(n2). Could have implemented the hash map solution which will solve it in O(n).
7. Patience Sorting and LIS in O(n log n) time.
8. Coin Change Problem 1) Solutions that do not contain mth coin (or Sm).
   2) Solutions that contain at least one Sm.
   Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).
9. Subset Sum isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||
                              isSubsetSum(arr, n-1, sum-set[n-1])
10. http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
12. sd
13. sd