Dynamic Programming (DP)

1. 1. Climbing Stairs

      1. Problem Statement:

         You are climbing a staircase that has n steps.
         Each time you can climb either 1 step or 2 steps.

         Your task: Count how many distinct ways you can reach the top.

         Input:

         • An integer n representing the total number of steps (n ≥ 0)

         Output:

         • An integer representing the number of distinct ways to climb to the top

         Examples:

         Input (n)	Output	Explanation
         1	1	Only one way: [1]
         2	2	[1+1], [2]
         3	3	[1+1+1], [1+2], [2+1]
         4	5	[1+1+1+1], [2+2], [1+1+2], [1+2+1], [2+1+1]

      2. Solution – https://gitlab.com/gsugiart/usaco_curriculum/-/blob/master/src/ClimbingStairs.java?ref_type=heads
   2. Coin Change (Count the Number of Ways)

      1. You are given a list of coin denominations and a target amount.

         Your task: Count how many different ways you can make up that amount using unlimited coins from the list.

         You may use each coin as many times as you want.

         Input:

         • An integer amount (amount ≥ 0)

         • An array coins[] of positive integers

         Output:

         • An integer representing the number of distinct combinations to make up the amount

         Examples:

         Example 1:

         coins = [1, 2, 5] amount = 5


         ✅ Output: 4

         ✅ Explanation:

         • [1+1+1+1+1]

         • [1+1+1+2]

         • [1+2+2]

         • [5]

         Example 1 explanation

         Goal:

         • dp[i] represents the number of combinations to make amount i.

         • You iterate over each coin, and for each coin, you build up the ways to make amounts from coin up to amount.

         ---

         Step-by-Step Example:

         Let’s use:

         int[] coins = {1, 2, 5};
int amount = 5;


         Initialize:

         dp = [1, 0, 0, 0, 0, 0] // dp[0] = 1 (base case)


         ---

         First Pass: coin = 1

         Update from index 1 to 5:

         • dp[1] += dp[0] → 1

         • dp[2] += dp[1] → 1

         • dp[3] += dp[2] → 1

         • dp[4] += dp[3] → 1

         • dp[5] += dp[4] → 1

         Now:

         dp = [1, 1, 1, 1, 1, 1]

         ➡️ All amounts can be made with just 1-coin combinations.

         ---

         Second Pass: coin = 2

         Update from index 2 to 5:

         • dp[2] += dp[0] → 1 + 1 = 2

         • dp[3] += dp[1] → 1 + 1 = 2

         • dp[4] += dp[2] → 1 + 2 = 3

         • dp[5] += dp[3] → 1 + 2 = 3

         Now:

         dp = [1, 1, 2, 2, 3, 3]

         ➡️ Includes combinations using coins of 1 and 2.

         ---

         Third Pass: coin = 5

         Update only dp[5]:

         • dp[5] += dp[0] → 3 + 1 = 4

         Now:

         dp = [1, 1, 2, 2, 3, 4]

         ➡️ You now also include combinations that use the 5-coin.

         ---

         ✅ Final Answer:

         return dp[5]; // 4


         There are 4 combinations to make 5:

         1. 1 + 1 + 1 + 1 + 1

         2. 1 + 1 + 1 + 2

         3. 1 + 2 + 2

         4. 5

         ---

         Why the Loop Order Matters

         You loop over coins first, then amounts, to ensure:

         • Each combination is only counted once

         • You avoid counting permutations like 1+2+2 and 2+1+2 as different

         This makes it a combinations solution, not permutations.

      2. Solution – https://gitlab.com/gsugiart/usaco_curriculum/-/blob/master/src/CoinChange.java?ref_type=heads