# Dynamic Programming vs Greedy Algorithms

What is an algorithm? An algorithm is a step by step method of achieving an end result. Different algorithms can achieve the same result in difference ways and taking into account different costs (eg time vs space).

In some cases an optimal solution is required. This is an optimization problem. In this case we don't care about getting just any result, we want the best result. An optimization problem is a problem where we have a goal to achieve but we also want to achieve the goal at a minimum cost. Greedy Algorithms and Dynamic Programming Algorithms can be used to find these.

## Greedy Algorithms

Greedy Algorithm aims to get the best result by picking seemingly best choice at each stage. It makes a locally optimum choice with the hope of finding a global optimum. With a greedy algorithm we never consider look into the future to pick the next best step. we just see what we see right now and make the best choice. And we never go back in time to make a different choice - we never reconsider our choices once we've made them. Because of this greedy algorithms can be considered "short sighted" and "non-recoverable".

They are best for simple problems. Note that because of this, greedy algorithms can fail to find the best result.

### Basic greedy algorithm example - change making

```C = [25, 15, 1] # ordered list of coin values
n = 30 # goal

print n
print

i = 0
while n != 0:
if n-C[i] >=0:
n = n-C[i] # take (n-C[i]) largest amount you can at each step (greedy)
print "%s - %s"%(n, C[i])
elif i<len(C)-1: # if you can't take this, means to go smaller piece
i = i+1
else:
print "no sol"
break
```

You want to make 30 cents in change, and you have amounts of 25, 15 and 1 cent pieces in whic you make this with. You want to use the least amount of coins. A greedy algorithm would take the largest amount you can at each step. So for the first step you would take a 25 cent piece. This leaves 4 cents remaning to make up. This is made up with 5 counts of 1 cent pieces. In total 6 coins are used.

```30

5 - 25
4 - 1
3 - 1
2 - 1
1 - 1
0 - 1
```

### A more complicated example

Trying to solve this: http://community.topcoder.com/stat?c=problem_statement&pm=2977&rd=5880

"Find the maximum number of disjoint time intervals that can be chosen such that each interval is of duration 1 second or less and contains button presses from at least 3 different judges. Two intervals are disjoint if every time within one interval is strictly less than every time in the other. We give the boxer credit for one punch during each interval."

How this solves it is that is starts from the minimum value and grows that interval until it hits 1000 milisecs or encounters hits from 3 judges. Then in tries to shrink this interval in a way that the previous property still remains true (hits from 3 different judges).

```import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;

public class boxing {
public static void main(String args[]) {

int[] a = new int[]{    1, 2, 3, 4, 5, 6 };
int[] b = new int[]{    1, 2, 3, 4, 5, 6, 7 };
int[] c = new int[]{    1, 2, 3, 4, 5, 6 };
int[] d = new int[]{ 0, 1, 2 };
int[] e = new int[]{    1, 2, 3, 4, 5, 6, 7, 8 };
System.out.println("**");
maxCredit(a, b, c, d, e);

a = new int[]{100,200,300,1200,6000};
b = new int[]{};
c = new int[]{900,902,1200,4000,5000,6001};
d = new int[]{0,2000,6002};
e = new int[]{1,2,3,4,5,6,7,8};

System.out.println("**");
maxCredit(a, b, c, d, e);

a = new int[]{5000,6500};
b = new int[]{6000};
c = new int[]{6500};
d = new int[]{6000};
e = new int[]{0,5800,6000};

System.out.println("**");
maxCredit(a, b, c, d, e);
}

public static int maxCredit(int[] a, int[] b, int[] c, int[] d, int[] e) {
//grow
//find smallest
smallest(a, b, c, d, e);  //need to know when three different arrays used, then remove from back.
return 0;
}

public static int smallest(int[] a, int[] b, int[] c, int[] d, int[] e) {
Comparator<element> comparator = new elementc();
PriorityQueue<element> queue = new PriorityQueue<element>(5, comparator);
ArrayList<element> feed = new ArrayList<element>();

try{ queue.add(new element("a", a, a, 0)); }catch(Exception f){}
try{ queue.add(new element("b", b, b, 0)); }catch(Exception f){}
try{ queue.add(new element("c", c, c, 0)); }catch(Exception f){}
try{ queue.add(new element("d", d, d, 0)); }catch(Exception f){}
try{ queue.add(new element("e", e, e, 0)); }catch(Exception f){}

for (int i = 0; i < a.length + b.length + c.length + d.length + e.length; i++) {
element x = queue.remove();
x.index++;
if (x.index < x.all.length) {
}
}
process(feed);
return 0;
}

public static void process(ArrayList<element> feed) {
System.out.println(feed);
ArrayList<element> uniq = new ArrayList<element>();
ArrayList<String> dupes = new ArrayList<String>();

ArrayList<element> split = new ArrayList<element>();
int startValue = -1;
int endValue = -1;
for (element e : feed) {
//System.out.println("Grabbed new element "+ e + " startValue="+startValue);
if(e.value>startValue && e.value - startValue < 999 ) {

for ( element f : uniq) {
if(e.value == f.value) {
if(dupes.indexOf(f.judge)<0) {
}
if(dupes.indexOf(e.judge)<0) {
}
if(dupes.size()==3){
//System.out.println("dupes"+dupes);
dupes = new ArrayList<String>();
//System.out.println("dupes cleared");

//System.out.println("contents of split1:"+split);
clean(split);
split = new ArrayList<element>();
//System.out.println("split cleared");

startValue = e.value;

//System.out.println("startValue reset to"+startValue);
break;
}
}
}
}
else if(e.value - startValue >= 999) {
//System.out.println("Difference was too great:"+(e.value-startValue));

endValue = (startValue + 1001 + 500) / 1000 * 1000; //round nearest sec
//System.out.println("Lets end this split: endValue="+endValue);

startValue += 1000;
//System.out.println("Lets take previous starting value and add 1000 to it: startValue="+startValue);

if(split.size()!=2) {
//System.out.println("split2"+split);
clean(split);
split = new ArrayList<element>();
//System.out.println("emptied split2 and started new with: "+(endValue+1));
}else{
//System.out.println("split3"+split);
//System.out.println("is empty. no actual elements in here");
split = new ArrayList<element>();
//System.out.println("emptied split3 and started new with: "+(endValue));
endValue = startValue+1000;
//System.out.println("endValue set to: "+endValue);
}
startValue = endValue-1;
//System.out.println("startValue set to: "+startValue);

}
}
//System.out.println("split3"+split);
clean(split);
//System.out.println("end value"+endValue);
}

public static void clean(ArrayList<element> split) {
//System.out.println("Cleaning..."+split);

//needs contain 3 diff judges.
//elim from front unnec

if(split.size()>3) {

while(true){split.remove(0);
ArrayList<String> dupes = new ArrayList<String>();
for (element q:split){

if(dupes.indexOf(q.judge)<0) {
}

}

if(dupes.size()>=3) {
//System.out.println("OK!");
//System.out.println(split);
break;
}
}
}
if (split.size()==3) {
ArrayList<String> dupes = new ArrayList<String>();
for (element q:split){

if(dupes.indexOf(q.judge)<0) {
}

}
if(dupes.contains("x")){
//System.out.println("ok!");
}
else if(dupes.size()!=3) {
//System.out.println("Not OK!");
//	System.out.println(split);
return;

}
}
System.out.println("Done!"+split.get(0).value+"-"+split.get(split.size()-1).value);
}
}

class element {
public String judge;
public int[] all;
public int value;
public int index;

public element(String judge, int[] all, int value, int index) {
this.judge = judge;
this.all = all;
this.value = value;
this.index = index;
}
public String toString() {
return ""+judge+") "+value;
}

public boolean equals(element e){
return this.value == e.value;
}

}

class elementc implements Comparator<element> {
public int compare(element x, element y) {
if (x.value < y.value) {
return -1;
}
if (x.value > y.value) {
return 1;
}
return 0;
}
}
```

### Dijkstra's algorithm

Let's take another look at Dijkstra's Algorithm.

We use Dijkstra's Algorithm because we want the shortest path from the start node to the end node. If we didn't want an optimal path we could just use dfs or bfs. This would get a path, but not necessarily the best path.

Why is Dijkstra's Algorithm considered a greedy algorithm? Because to find the shortest path it picks the nearest unvisited node at each iteration. And once visited, its distance will never be updated.

We don't do is consider every possible path to a node, some nodes may go unexplored. Sometimes the solution may not even be optimal. So this is not considered dynamic programming. However they both do share the commonality of optimal substructure. We use this property to print the path when finished.

```			while previous[smallest]:
path.append(smallest)
print "%s:%s"%(smallest,previous[smallest])
smallest = previous[smallest]
path.append(smallest)
return path
```

We know that A - B - C - D is an optimal route from A to D. Then A - B - C is an optimal route from A to C.

This is not unlike the printing change in the dynamic programming example below.