Strategies Solving DP

Dynamic programming was hard at first, but it became easier if you have right approach to tackle given problem.

First, finding a optimal subproblem is the key, and then finding an way to express the given problem effectively.
Second, find a relationship between between subproblems. Usually, it is from smaller to larger subproblem repetitively.

Edit Distance

Find an minimum edit distance between two strings. One edit operation can be insertion, deletion, and substitution at the position from one string to another.

Ideas to solve
1. What is the smallest subproblem?
2. How many variables involved in subproblems?

Cautions:
1. Be careful when dealing with edge cases, and not getting index out of bound error.

Every dynamic programming problems has an directed acyclic graphs, and each node represents a subproblem.

Dynamic Programming

Dynamic Programming is an advanced problem solving technique that utilizes the answers of smaller subproblems. It start with smallest subproblem and iteratively find larger problems one by one, and save the results of each subproblem and use it for larger problems. When we go from smaller and larger subproblem, we need to find a relationship between these. Hence, the key to solve an algorithmatic problem with DP, we need to build abilities to find optimal subproblem structure and the link between them.

The first example is Longest increasing subsequences.
Input: a sequence of numbers a1,...,an,
Output: an increasing subsequence of greater length.
A subsequence is any subset of these numbers taken in order.

The longest subsequence of 5,2,7,6,3,8,9,7 is 2,3,8,9

At first attempt, I spent a lot of hours and did not come up with correct algorithm. Before we tackle into coding, always write your algorithm in a pseudocode. And check if the algorithm looks correct.
Here are few things to remember.
0. Don't look at answer. Solve it on your own.
1. Base condition
2. Did you find optimal subproblem? How to index subproblem?
3. Did you save the result of subproblems, and reuse it in later calculation? What's the format of result?
4. Did you find correct relationship between subproblems ( from smaller and larger)
5. How many functions needed?

It is been a while I am solving this kind of problem again, and it took me almost three hours to get the correct algorithm.

Here is my pseudocode and a program in Java.

1. Base condition
Result[0] = input[0]

2. Optimal subproblem
LongSub(0),...,LongSub(n-1)

3. Result format:
Use Map>

4. Relationship
LongSub(v) = maxSize ( LongSub(u),v), for all v > u where u is less than v by index position.

Java program

public class LongestSub {

public static void main (String[] args) {

System.out.println();

List list1 = new ArrayList();

list1.add(5);

list1.add(2);

list1.add(8);

list1.add(6);

list1.add(3);

list1.add(6);

list1.add(9);

list1.add(7);

System.out.println(list1);

List list2 = findLongSub(list1,8);

Collections.sort(list2);

System.out.println(list2);

}

public static List findLongSub(List input, int n)

{

Map> resultmap = new HashMap>();

List first = new ArrayList();

first.add(input.get(0));

resultmap.put(0, first);

List result = longSub(resultmap, input, n, n-1);

return result;

}

public static List longSub(Map> map, List input, int n, int i)

{

List result = new ArrayList();

result.add(input.get(i));

if (i==0)

{

return result;

}

List subArray = new ArrayList();

subArray.addAll(input.subList(0, i));

int maxsize = 0;

List intermediate = new ArrayList();

for (Integer j=0;j<subArray.size();j++)

{

intermediate.clear();

intermediate.add(input.get(i));

if (input.get(i) > subArray.get(j))

{

List temp = null;

if (map.containsKey(j))

temp = map.get(j);

else

temp = longSub(map, input,n,j);

if (temp.size() + 1 > maxsize)

{

maxsize = temp.size() + 1;

intermediate.addAll(temp);

result.clear();

result.addAll(intermediate);

}

}

}

map.put(i, result);

return result;

}

}

Detect a cycle in linked list

The problem is to detect a cycle in a linked list, and find a start node of the cycle.
We have a linked list.

First, we have to know how many nodes in the cycle. To find out, we use two pointers with different speed and stop when the node is the same. Then use only one pointer and move forward, and save current node and count the node, then stop when the pointer is in the same node.
Second, use two pointers, each apart the the number of nodes in the cycle. When we met the same node while moving two pointers, that is the start node of the cycle.
Complete source in Java is in the below.


 import java.io.*;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     myCode code = new myCode();
     code.doWork();
   }
   public void doWork() {
     Node node = new Node(1);
     Node temp1 = new Node(2);
     Node temp2 = new Node(3);
     Node temp3 = new Node(4);
     Node temp4 = new Node(5);
     node.next = temp1;
     temp1.next = temp2;
     temp2.next = temp3;
     temp3.next = temp4;
     temp4.next = temp2;
     int cycle = detect(node);
     int start = findStart(node,cycle);
     System.out.println(cycle);
   }
   public int detect(Node head) {
     Node first = head;
     Node second = head;
     int count = 0;
     boolean found = false;
     while (first != null && second.next != null) {
       first = first.next;
       second = second.next.next;
       if (first.value == second.value) {
         found = true;
         break;
       }
     }
     if (found) {
       int start = first.value;
       while (first != null) {
         first = first.next;
         count++;
         if (first != null && first.value == start) {
           return count;
         }
       }  
     }
     return -1;
   }
   public int findStart(Node head, int cycle) {
     Node first = head;
     Node second = head;
     for (int i=0;i<cycle;i++) {
       second = second.next;
     }
     while (first.value != second.value) {
       first = first.next;
       second = second.next;
     }
     return second.value;
   }
   class Node {
     int value;
     Node next = null;
     public Node(int val) {
       value = val;
     }
   }
 }

Quick Sort

Quick sort runs O(nlogn). It is similar with merge sort, but it differs by selecting a pivot and partition the array based on the pivot element.
Let's look at an example.
We have an integer array {7,5,9,10,1,6,13,2,8},  and choose pivot element. In this case we choose pivot as the last element, i.e., 8.
The rearrange the left and right based on pivot.

use index i=0, j=array.length-1
{7,5,2,6,1}            {8}              {10,13,9}
{}  {1} {7,5,2,6}   {8}              {}  {9}  {10,13}
{1} {2,5} {6} {7}  {8}              {9} {10} {13}
{1} {2} {5} {6} {7}  {8}           {9} {10} {13}
{1,2,5,6,7,8,9,10,13}

The code in Java is in the below. Please be careful when you partition the array based on the pivot.
For example, if you partition an array {5,3,7}, and set the pivot as the last element, it end up with i=1,j=1, and pivot = 7. Here, you only swap if the pivot is less than i-th element.

 import java.io.*;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     int[] input = {5,7,9,10,1,6,13,2,8};
     quickSort(input, 0, input.length-1);
     System.out.println("sorted list:");
     for (int i=0;i<input.length;i++) {
       System.out.print(input[i] + ",");
     }
   }
   public static void quickSort(int[] array, int start, int end) {
     if (end - start < 1) {
       return;
     } else if ((end - start) == 1) {
       if (array[start] > array[end]) {
         int temp = array[start];
         array[start] = array[end];
         array[end] = temp;
       }
     } else {
       partition(array, start, end);
     }
   }
   public static void partition(int[] array, int start, int end) {
     int pivot = array[end];
     int i=start;
     int j=end-1;
     while (i<j) {
       if (array[i]>pivot && array[j] < pivot) {
         int temp = array[i];
         array[i] = array[j];
         array[j] = temp;
         i++;
         j--;
       } else if (array[i] < pivot) {
         i++;
       } else if (array[j] > pivot) {
         j--;
       }
     }
     //swap i to end
     if (array[i] > array[end]) {
       int temp2 = array[i];
       array[i] = array[end];
       array[end] = temp2;
     }
     quickSort(array,start,i);
     quickSort(array,i+1,end);
   }
 }

Merge Sort

Merge sort runs in O(nlogn). It uses an divide and conquer. First, it divide the original array into two sub array until it has only 1 element in the array. Then, it merge the sub-arrays by sorting it in correct order.
The example will be more clear.
We have an integer array {7,5,9,10,1,6,13,2,8}, and by applying merge sort, we have the following sequences.

The code implemented in Java is in the below.


 import java.io.*;
 import java.util.Arrays;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     int[] input = {7,5,9,10,1,6,13,2,8};
     int[] output = mergeSort(input);
     System.out.println("sorted list:");
     for (int i=0;i<output.length;i++) {
       System.out.print(output[i] + ",");
     }
   }
   public static int[] mergeSort(int[] array) {
     int middle = array.length/2;
     if (array.length < 2) {
       return array;
     } else {
       int[] left = mergeSort(Arrays.copyOfRange(array, 0, middle));
       int[] right = mergeSort(Arrays.copyOfRange(array, middle, array.length));
       return merge(left,right);
     }
   }
   public static int[] merge(int[] a, int[] b) {
     int len = a.length + b.length;
     int[] result = new int[len];
     int i=0;
     int j=0;
     while (i<a.length || j<b.length) {
       if (j >= b.length || (i < a.length && a[i]<b[j])) {
         result[i+j] = a[i];
         i++;
       } else {
         result[i+j] = b[j];
         j++;
       }
     }
     return result;
   }
 }

Chicken McNugget Theorem

The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers m,n, the greatest integer that cannot be written in the form am + bn for nonnegative integers a, b is mn-m-n.

For example, given two integers 4 and 7, the greatest integers that cannot be written in the form of a*4 + b*7 for nonnegative integers a,b is 4*7-4-7 = 17.

Reference: https://www.artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem