Greedy vs Dynamic Programming

Dynamic Programming Choice

1. Optimal substructure: optimal solutions to a problem incorporate optimal solutions to related subproblem, which you may solve independently
2. Overlapping subproblems : Memoization

Applications: Searching for an optimization problem among many possible solutions.
Minimum or maximum value such as:

• Rod cutting for a maximum revenue
• Longest subsequence

Introduction to Algorithmes (Cormen) Chap 14 Dynamic Programming

Greedy Algorithm Choice

Eating largest cookies actually good thing to do when

1. Optimal substructure
2. locally optimal choices lead to globally optimal solution

Applications

• Minimum Spanning Tree
• Prim's algorithm
• Kruscal's Algorithm

MIT Introduction algorithm (2015) Lecture 12 by Erik Demaine

Coin Change

Case 1: 동전이 배수 인 경우 -> Greedy T=O(n) Case 2: 동전이 배수가 아닌 경우 -> DP coins = [1,4,5] amount = 8

Leetcode 322 https://www.youtube.com/clip/UgkxmRU6B50goKoHrmbbsyDtsRfMR1lwpiX-