Climbing Stairs (Advanced)

This problem extends the classic climbing stairs by allowing jumps of any length, making it equivalent to a complete knapsack permutation problem.

Problem (Kamangar 57): Given m available step sizes, determine how many ways to reach stair n.

Dynamic Programming Approach

1. DP Array Definition: dp[j] represents the number of ways to reach step j.

2. Recurrence Formula: dp[j] accumulates the ways from previous positions:

dp[j] += dp[j - step];

3. Initialization: dp[0] = 1 (one valid way to stay at ground level).

4. Traversal Order: For permutation problems, iterate背包 first (outer loop), then items (inner loop). Complete knapsack uses forward traversal.

Key Point: Always validate before updating the recurrence formula in complete knapsack permutation scenarios.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int steps, target;
    while (cin >> target >> steps) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int j = 1; j <= target; j++) {
            for (int k = 1; k <= steps; k++) {
                if (j >= k) {
                    dp[j] += dp[j - k];
                }
            }
        }
        cout << dp[target];
    }
    return 0;
}

Coin Change

Leetcode 322: Given coin denominations, find the minimum coins needed to make up a target amount.

Solution

1. DP Array: dp[j] = minimum coins required to reach amount j.

2. Recurrence:

dp[j] = min(dp[j], dp[j - coin] + 1);

3. Initialization: dp[0] = 0; all other positions set to INT_MAX.

4. Traversal: Outer loop iterates coins; inner loop traverses amounts forward (complete knapsack).

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

Critical Check: The condition dp[j - coin] != INT_MAX prevents overflow when certain amounts cannot be formed.

Perfect Squares

Leetcode 279: Given integer n, find the minimum number of perfect squares that sum to n.

This problem mirrors coin change, where each perfect square (1, 4, 9, 16...) serves as a "coin."

Solution

1. DP Array: dp[j] = minimum perfect squares needed to sum to j.

2. Recurrence:

dp[j] = min(dp[j], dp[j - square] + 1);

where square = i * i.

3. Initialization: dp[0] = 0; remaining entries initialized to INT_MAX.

4. Traversal: Outer loop generates valid squares; inner loop processes amounts forward.

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 1; i * i <= n; i++) {
            int square = i * i;
            for (int j = square; j <= n; j++) {
                if (dp[j - square] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - square] + 1);
                }
            }
        }
        return dp[n];
    }
};

Note: Since 1 is always a perfect square, every positive integer can be represented—this guarantees a valid solution exists.