Advanced Stair Climbing

Problem Statement: Given a staircase with n steps, determine the number of distinct ways to reach the top if you can climb between 1 and m steps at a time. Each step increment can be reused any number of times.

Solution Approach

This problem is modeled as a complete knapsack problem where step increments represent items and the top step represents the knapsack capacity. The solution involves:

1. DP Array Definition: Let dp[i] rerpesent the number of ways to reach step i.
2. Recurrence Relation: For each step i, sum the solutions from all possible previous steps within m steps: dp[i] += dp[i - j] where 1 ≤ j ≤ m.
3. Initialization: dp[0] = 1 (base case for ground level). All other entries start as 0.
4. Iteration Order: Outer loop iterates through steps (knapsack capacity), inner loop through possible step increments (items). Inner loop processes in forward direction for unlimited reuse.

int climbStairs(int n, int m) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int step = 1; step <= n; step++) {
        for (int jump = 1; jump <= m; jump++) {
            if (step >= jump) {
                dp[step] += dp[step - jump];
            }
        }
    }
    return dp[n];
}

Coin Change Problem

Problem Statement: Given coins of various denominations and a total amount, find the minimum number of coins required to make up that amount. Return -1 if impossible. Coins can be used infinitely.

Solution Approach

Modeled as a complete knapsack problem:

1. DP Array Definition: dp[j] represents the minimum coins needed for amount j.
2. Recurrence Relation: For each coin, update the minimum coins required: dp[j] = min(dp[j], dp[j - coin] + 1).
3. Initialization: dp[0] = 0. All other entries initialize to a large value (INT_MAX).
4. Iteration Order: Both coin-first or amount-first iterations are valid. Below uses coin-first with forward processing.

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int coin : coins) {
        for (int current = coin; current <= amount; current++) {
            if (dp[current - coin] != INT_MAX) {
                dp[current] = min(dp[current], dp[current - coin] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}