Algorithms - lesson 5 | HackIndia Skills

Key point

Main choice

Greedy makes the best-looking choice now and never goes back. Dynamic programming stores answers to smaller states because the same subproblems come back again.

Use greedy only when you can explain why the local choice is safe. Use DP when you need to try choices and keep the best result.

Greedy signals

Greedy problems often ask for minimum coins, maximum activities, intervals, jumps, or scheduling. But the topic name can trick you in placements.

Ask: after I pick this option, can any better full answer require me to undo it? If yes, greedy is unsafe.

DP signals

DP fits when you see words like count ways, maximum profit, minimum cost, subsequence, partition, or choose or skip. You usually have an index, remaining capacity, previous choice, or amount as state.

A DP solution needs three things: state, transition, and base case. Then add memoization or build a table.

Common mistake

Common trap

Do not choose greedy just because it passes the sample tests. Samples are small and friendly.

For Indian coin values, greedy works for many everyday amounts. But for a custom set like [1, 3, 4], amount 6, greedy picks 4+1+1 as 3 coins. DP finds 3+3 as 2 coins.

Example

DP coin change

This is a good repo problem because it clearly shows why DP is needed. Save it as dp/coin_change.py or similar.

The state is amount x. dp[x] means the minimum coins needed to make x.

def min_coins(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for coin in coins:
            if coin <= x:
                dp[x] = min(dp[x], 1 + dp[x - coin])

    return -1 if dp[amount] == INF else dp[amount]

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

Your to-do

Pick the approach

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Write the brute-force choice first in one sentence: choose, skip, take next, or stop.
Check if the best local choice can be proved safe for every input.
Use greedy if one sorted order plus one pass solves it safely.
Use DP if the same state appears again, like index and remaining amount.
Write time and space complexity before you move to the next problem.

0 of 5 done

Tip

Use AI carefully

You can ask ChatGPT, Gemini, or Claude: “Is this problem greedy or DP? Give the state or greedy proof, but do not write code first.”

Check the answer yourself. For greedy, demand a short proof or counterexample. For DP, check that the state contains enough information to make future decisions.