DYNAMIC PROGRAMMING:  "Intelligent Trial And Error".  Using a table to keep track of repeated subproblems, you essentially try every possible combination to generate the answer.

GREEDY ALGORITHMS:  You make the best choice for now, and voila, you still end up with a correct answer.  (Short term strategy actually works for once.)

Kruskal's Algorithm for Minimum Spanning Tree

The trick to Greedy Algorithms is not coming up with the correct algorithm--that's pretty easy.  The trick is knowing that the greedy algorithm is appropriate in the first place.

So, when I give you Greedy problems, you have to be able to prove that the Greedy Algorithm actually works in the first place.

So, with the Kruskal's Algorithm, I begin by choosing the smallest edge.  Is this a good starting strategy?  Yes, and I prove this by comparing my final answer with someone else's final answer.

Assume Algorithm B did NOT pick the smallest edge first and ended up with a spanning tree with a smaller edge weight sum than mine.

To prove a contradiction, I don't literally have to prove that my tree is better than B's tree.  All I have to prove is that B's tree isn't the best.  If I can make an improvement to B's tree, then the B's tree isn't the best, and that's the contradiction.

I take the edge I picked and I add it to B's tree.  This introduces a cycle.  I can break the cycle by removing any edge of it.  Now, if I remove an edge that's larger than the edge I added, then by removing I've lowered B's edge-weight-sum, so I've improved it.  I can't remove an edge smaller than mine, since mine is the smallest.  I can remove an edge that's the same length as mine, and would cause no change to the edge-weight sum, but even then, I've demonstrated that B is using the smallest edge in his tree, just like I'm using in mine.