Advanced

#include <stdio.h>
#include <string.h>

// => Use long long for large Fibonacci values; fib(50) exceeds 32-bit range
long long cache[101];
// => cache[i] stores fib(i); -1 means "not yet computed"
int cache_init = 0;

long long fib_memo(int n) {
    if (!cache_init) {
        memset(cache, -1, sizeof(cache));
        // => Initialize all entries to -1 (uncomputed sentinel)
        cache_init = 1;
    }
    if (cache[n] != -1) {
        return cache[n];              // => O(1) lookup: already solved this subproblem
    }
    if (n <= 1) {
        return cache[n] = n;          // => Base cases: fib(0)=0, fib(1)=1
    }
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2);
    // => Store result before returning — this is the memoization step
    // => Without this, fib(50) would require ~2^50 recursive calls (~1 quadrillion)
    return cache[n];                  // => Return cached result
}

int main(void) {
    printf("%lld\n", fib_memo(10));   // => Output: 55
    printf("%lld\n", fib_memo(50));   // => Output: 12586269025 (computed instantly due to cache)
    // => fib(100) exceeds long long range; Python handles arbitrary precision natively
    return 0;
}

package main

import "fmt"

// => cache stores computed Fibonacci values; 0 means "not yet computed" (works since fib(0)=0 is a base case)
var cache [101]int64
var computed [101]bool

func fibMemo(n int) int64 {
    if computed[n] {
        return cache[n] // => O(1) lookup: already solved this subproblem
    }
    if n <= 1 {
        computed[n] = true
        cache[n] = int64(n) // => Base cases: fib(0)=0, fib(1)=1
        return cache[n]
    }
    cache[n] = fibMemo(n-1) + fibMemo(n-2)
    // => Store result before returning — this is the memoization step
    // => Without this, fib(50) would require ~2^50 recursive calls (~1 quadrillion)
    computed[n] = true
    return cache[n] // => Return cached result
}

func main() {
    fmt.Println(fibMemo(10)) // => Output: 55
    fmt.Println(fibMemo(50)) // => Output: 12586269025 (computed instantly due to cache)
    // => fib(100) exceeds int64 range; Python handles arbitrary precision natively
}

import sys
# => sys provides setrecursionlimit to allow deep recursion for large n
sys.setrecursionlimit(10000)
# => Default Python recursion limit is 1000; fib(5000) needs ~5000 frames

def fib_memo(n, cache={}):
    # => cache is a mutable default argument — persists across calls (intentional)
    # => Python evaluates default arguments once at function definition time
    if n in cache:
        return cache[n]             # => O(1) lookup: already solved this subproblem
    if n <= 1:
        return n                    # => Base cases: fib(0)=0, fib(1)=1
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    # => Store result before returning — this is the memoization step
    # => Without this, fib(50) would require ~2^50 recursive calls (~1 quadrillion)
    return cache[n]                 # => Return cached result

print(fib_memo(10))   # => Output: 55
print(fib_memo(50))   # => Output: 12586269025 (computed instantly due to cache)
print(fib_memo(100))  # => Output: 354224848179261915075
# => Without memoization, fib(100) would run for longer than the age of the universe

import java.util.HashMap;
import java.util.Map;

public class FibMemo {
    // => cache stores computed Fibonacci values
    private static Map<Integer, Long> cache = new HashMap<>();

    public static long fibMemo(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);              // => O(1) lookup: already solved this subproblem
        }
        if (n <= 1) {
            return n;                         // => Base cases: fib(0)=0, fib(1)=1
        }
        long result = fibMemo(n - 1) + fibMemo(n - 2);
        // => Store result before returning — this is the memoization step
        // => Without this, fib(50) would require ~2^50 recursive calls (~1 quadrillion)
        cache.put(n, result);
        return result;                        // => Return cached result
    }

    public static void main(String[] args) {
        System.out.println(fibMemo(10));      // => Output: 55
        System.out.println(fibMemo(50));      // => Output: 12586269025 (computed instantly due to cache)
        // => fib(100) exceeds long range; Python handles arbitrary precision natively
    }
}

#include <stdio.h>

// => Returns max of two integers
int max(int a, int b) { return a > b ? a : b; }

int knapsack_01(int weights[], int values[], int n, int capacity) {
    // => weights[i] and values[i] describe item i
    // => capacity is the maximum weight the knapsack can hold
    int dp[n + 1][capacity + 1];
    // => dp[i][w] = max value using first i items with weight limit w
    // => All initialized to 0: no items or no capacity -> zero value

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;                 // => Base case
            } else {
                // => Option 1: skip item i (don't include it)
                dp[i][w] = dp[i - 1][w];     // => Inherit value from previous row
                int wi = weights[i - 1];      // => Weight of current item (0-indexed)
                int vi = values[i - 1];       // => Value of current item (0-indexed)
                if (wi <= w) {
                    // => Option 2: include item i if it fits
                    int include = dp[i - 1][w - wi] + vi;
                    // => dp[i-1][w-wi]: best value with remaining capacity after taking item i
                    dp[i][w] = max(dp[i][w], include);
                    // => Take the better of skipping or including
                }
            }
        }
    }
    return dp[n][capacity];                   // => Maximum achievable value
}

int main(void) {
    int weights[] = {2, 3, 4, 5};
    int values[]  = {3, 4, 5, 6};
    int W = 5;
    printf("%d\n", knapsack_01(weights, values, 4, W)); // => Output: 7
    // => Best: item 0 (weight=2, value=3) + item 1 (weight=3, value=4) = total weight 5, value 7
    return 0;
}

package main

import "fmt"

func knapsack01(weights, values []int, capacity int) int {
    // => weights[i] and values[i] describe item i
    // => capacity is the maximum weight the knapsack can hold
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    // => dp[i][w] = max value using first i items with weight limit w
    // => All initialized to 0: no items or no capacity -> zero value

    for i := 1; i <= n; i++ { // => Process each item 1..n
        for w := 0; w <= capacity; w++ { // => For each capacity 0..W
            // => Option 1: skip item i (don't include it)
            dp[i][w] = dp[i-1][w] // => Inherit value from previous row
            wi := weights[i-1]    // => Weight of current item (0-indexed)
            vi := values[i-1]     // => Value of current item (0-indexed)
            if wi <= w {
                // => Option 2: include item i if it fits
                include := dp[i-1][w-wi] + vi
                // => dp[i-1][w-wi]: best value with remaining capacity after taking item i
                if include > dp[i][w] {
                    dp[i][w] = include
                }
                // => Take the better of skipping or including
            }
        }
    }
    return dp[n][capacity] // => Maximum achievable value
}

func main() {
    weights := []int{2, 3, 4, 5}
    values := []int{3, 4, 5, 6}
    W := 5
    fmt.Println(knapsack01(weights, values, W)) // => Output: 7
    // => Best: item 0 (weight=2, value=3) + item 1 (weight=3, value=4) = total weight 5, value 7
}

def knapsack_01(weights, values, capacity):
    # => weights[i] and values[i] describe item i
    # => capacity is the maximum weight the knapsack can hold
    n = len(weights)                          # => n is number of items
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    # => dp[i][w] = max value using first i items with weight limit w
    # => dp is (n+1) x (capacity+1) to handle 0-item and 0-capacity base cases
    # => All initialized to 0: no items or no capacity → zero value

    for i in range(1, n + 1):               # => Process each item 1..n
        for w in range(capacity + 1):       # => For each capacity 0..W
            # => Option 1: skip item i (don't include it)
            dp[i][w] = dp[i - 1][w]        # => Inherit value from previous row
            wi = weights[i - 1]             # => Weight of current item (0-indexed)
            vi = values[i - 1]              # => Value of current item (0-indexed)
            if wi <= w:
                # => Option 2: include item i if it fits
                include = dp[i - 1][w - wi] + vi
                # => dp[i-1][w-wi]: best value with remaining capacity after taking item i
                dp[i][w] = max(dp[i][w], include)
                # => Take the better of skipping or including

    return dp[n][capacity]                  # => Maximum achievable value

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
W       = 5
print(knapsack_01(weights, values, W))      # => Output: 7
# => Best: item 0 (weight=2, value=3) + item 1 (weight=3, value=4) = total weight 5, value 7

public class Knapsack01 {
    public static int knapsack01(int[] weights, int[] values, int capacity) {
        // => weights[i] and values[i] describe item i
        // => capacity is the maximum weight the knapsack can hold
        int n = weights.length;               // => n is number of items
        int[][] dp = new int[n + 1][capacity + 1];
        // => dp[i][w] = max value using first i items with weight limit w
        // => All initialized to 0: no items or no capacity -> zero value

        for (int i = 1; i <= n; i++) {       // => Process each item 1..n
            for (int w = 0; w <= capacity; w++) { // => For each capacity 0..W
                // => Option 1: skip item i (don't include it)
                dp[i][w] = dp[i - 1][w];    // => Inherit value from previous row
                int wi = weights[i - 1];     // => Weight of current item (0-indexed)
                int vi = values[i - 1];      // => Value of current item (0-indexed)
                if (wi <= w) {
                    // => Option 2: include item i if it fits
                    int include = dp[i - 1][w - wi] + vi;
                    // => dp[i-1][w-wi]: best value with remaining capacity after taking item i
                    dp[i][w] = Math.max(dp[i][w], include);
                    // => Take the better of skipping or including
                }
            }
        }
        return dp[n][capacity];              // => Maximum achievable value
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values  = {3, 4, 5, 6};
        int W = 5;
        System.out.println(knapsack01(weights, values, W)); // => Output: 7
        // => Best: item 0 (weight=2, value=3) + item 1 (weight=3, value=4) = total weight 5, value 7
    }
}

#include <stdio.h>
#include <string.h>

void lcs(const char *s1, const char *s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m + 1][n + 1];
    // => dp[i][j] = LCS length of s1[:i] and s2[:j]
    // => Extra row/col for empty-string base cases (all zeros)
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                // => Characters match: extend LCS by 1
            } else {
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
                // => No match: take better of skipping a character from either string
            }
        }
    }

    // => Reconstruct the actual LCS string by backtracking through dp table
    char lcs_str[m + n + 1];
    int idx = 0;
    int i = m, j = n;                         // => Start from bottom-right corner
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs_str[idx++] = s1[i - 1];       // => This character is in the LCS
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;                              // => Move up: came from dp[i-1][j]
        } else {
            j--;                              // => Move left: came from dp[i][j-1]
        }
    }
    // => Reverse because we backtracked
    for (int l = 0; l < idx / 2; l++) {
        char tmp = lcs_str[l];
        lcs_str[l] = lcs_str[idx - 1 - l];
        lcs_str[idx - 1 - l] = tmp;
    }
    lcs_str[idx] = '\0';

    printf("%d\n", dp[m][n]);                 // => Output: 4
    printf("%s\n", lcs_str);                  // => Output: BCBA
}

int main(void) {
    lcs("ABCBDAB", "BDCABA");
    return 0;
}

package main

import "fmt"

func lcs(s1, s2 string) (int, string) {
    m, n := len(s1), len(s2) // => m=len(s1), n=len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    // => dp[i][j] = LCS length of s1[:i] and s2[:j]
    // => Extra row/col for empty-string base cases (all zeros)

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                // => Characters match: extend LCS by 1
            } else {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
                // => No match: take better of skipping a character from either string
            }
        }
    }

    // => Reconstruct the actual LCS string by backtracking through dp table
    lcsStr := []byte{}
    i, j := m, n // => Start from bottom-right corner
    for i > 0 && j > 0 {
        if s1[i-1] == s2[j-1] {
            lcsStr = append(lcsStr, s1[i-1]) // => This character is in the LCS
            i--
            j--
        } else if dp[i-1][j] > dp[i][j-1] {
            i-- // => Move up: came from dp[i-1][j]
        } else {
            j-- // => Move left: came from dp[i][j-1]
        }
    }
    // => Reverse because we backtracked
    for l, r := 0, len(lcsStr)-1; l < r; l, r = l+1, r-1 {
        lcsStr[l], lcsStr[r] = lcsStr[r], lcsStr[l]
    }
    return dp[m][n], string(lcsStr)
}

func main() {
    length, seq := lcs("ABCBDAB", "BDCABA")
    fmt.Println(length) // => Output: 4
    fmt.Println(seq)    // => Output: BCBA  (one valid LCS; others like BDAB also valid)
}

def lcs(s1, s2):
    m, n = len(s1), len(s2)                   # => m=len(s1), n=len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # => dp[i][j] = LCS length of s1[:i] and s2[:j]
    # => Extra row/col for empty-string base cases (all zeros)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                # => Characters match: extend LCS by 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                # => No match: take better of skipping a character from either string

    # => Reconstruct the actual LCS string by backtracking through dp table
    lcs_str = []
    i, j = m, n                               # => Start from bottom-right corner
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs_str.append(s1[i - 1])         # => This character is in the LCS
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1                            # => Move up: came from dp[i-1][j]
        else:
            j -= 1                            # => Move left: came from dp[i][j-1]
    lcs_str.reverse()                         # => Reverse because we backtracked
    return dp[m][n], "".join(lcs_str)

length, seq = lcs("ABCBDAB", "BDCABA")
print(length)   # => Output: 4
print(seq)      # => Output: BCBA  (one valid LCS; others like BDAB also valid)

public class LCS {
    public static void main(String[] args) {
        String s1 = "ABCBDAB", s2 = "BDCABA";
        int m = s1.length(), n = s2.length(); // => m=len(s1), n=len(s2)
        int[][] dp = new int[m + 1][n + 1];
        // => dp[i][j] = LCS length of s1[:i] and s2[:j]
        // => Extra row/col for empty-string base cases (all zeros)

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // => Characters match: extend LCS by 1
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    // => No match: take better of skipping a character from either string
                }
            }
        }

        // => Reconstruct the actual LCS string by backtracking through dp table
        StringBuilder lcsStr = new StringBuilder();
        int i = m, j = n;                    // => Start from bottom-right corner
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                lcsStr.append(s1.charAt(i - 1)); // => This character is in the LCS
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;                          // => Move up: came from dp[i-1][j]
            } else {
                j--;                          // => Move left: came from dp[i][j-1]
            }
        }
        lcsStr.reverse();                     // => Reverse because we backtracked

        System.out.println(dp[m][n]);         // => Output: 4
        System.out.println(lcsStr.toString()); // => Output: BCBA  (one valid LCS; others like BDAB also valid)
    }
}

#include <stdio.h>

// => Binary search: find leftmost position where tails[pos] >= num
int bisect_left(int tails[], int size, int num) {
    int lo = 0, hi = size;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (tails[mid] < num) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int lis_length(int nums[], int n) {
    int tails[n];
    // => tails[i] = smallest tail element of all increasing subsequences of length i+1
    // => tails is always sorted (maintained as invariant)
    int size = 0;

    for (int i = 0; i < n; i++) {
        int pos = bisect_left(tails, size, nums[i]);
        // => Binary search: find leftmost position where num can be inserted
        // => O(log n) per element instead of O(n) linear scan
        if (pos == size) {
            tails[size++] = nums[i]; // => num extends the longest subsequence found so far
        } else {
            tails[pos] = nums[i];    // => Replace: num is a better (smaller) tail for length pos+1
            // => This greedy replacement keeps tails as small as possible
            // => Smaller tails allow more elements to extend subsequences later
        }
    }
    return size;                     // => Length of tails = LIS length
}

int main(void) {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    printf("%d\n", lis_length(nums, 8)); // => Output: 4
    // => One LIS is [2, 3, 7, 18] or [2, 5, 7, 18] or [2, 3, 7, 101]
    return 0;
}

package main

import (
    "fmt"
    "sort"
)

func lisLength(nums []int) int {
    tails := []int{}
    // => tails[i] = smallest tail element of all increasing subsequences of length i+1
    // => tails is always sorted (maintained as invariant)

    for _, num := range nums {
        pos := sort.SearchInts(tails, num)
        // => Binary search: find leftmost position where num can be inserted
        // => O(log n) per element instead of O(n) linear scan
        if pos == len(tails) {
            tails = append(tails, num) // => num extends the longest subsequence found so far
        } else {
            tails[pos] = num // => Replace: num is a better (smaller) tail for length pos+1
            // => This greedy replacement keeps tails as small as possible
            // => Smaller tails allow more elements to extend subsequences later
        }
    }
    return len(tails) // => Length of tails = LIS length
}

func main() {
    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
    fmt.Println(lisLength(nums)) // => Output: 4
    // => One LIS is [2, 3, 7, 18] or [2, 5, 7, 18] or [2, 3, 7, 101]
    // => The tails array after processing: [2, 3, 7, 18] (not the actual LIS, but its length is correct)
}

import bisect
# => bisect provides binary search on sorted lists (standard library)

def lis_length(nums):
    tails = []
    # => tails[i] = smallest tail element of all increasing subsequences of length i+1
    # => tails is always sorted (maintained as invariant)

    for num in nums:
        pos = bisect.bisect_left(tails, num)
        # => Binary search: find leftmost position where num can be inserted
        # => O(log n) per element instead of O(n) linear scan
        if pos == len(tails):
            tails.append(num)       # => num extends the longest subsequence found so far
        else:
            tails[pos] = num        # => Replace: num is a better (smaller) tail for length pos+1
            # => This greedy replacement keeps tails as small as possible
            # => Smaller tails allow more elements to extend subsequences later

    return len(tails)               # => Length of tails = LIS length

nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_length(nums))             # => Output: 4
# => One LIS is [2, 3, 7, 18] or [2, 5, 7, 18] or [2, 3, 7, 101]
# => The tails array after processing: [2, 3, 7, 18] (not the actual LIS, but its length is correct)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LIS {
    public static int lisLength(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        // => tails[i] = smallest tail element of all increasing subsequences of length i+1
        // => tails is always sorted (maintained as invariant)

        for (int num : nums) {
            int pos = Collections.binarySearch(tails, num);
            if (pos < 0) pos = -(pos + 1);
            // => binarySearch returns -(insertion point)-1 when not found
            // => O(log n) per element instead of O(n) linear scan
            if (pos == tails.size()) {
                tails.add(num);              // => num extends the longest subsequence found so far
            } else {
                tails.set(pos, num);         // => Replace: num is a better (smaller) tail for length pos+1
                // => This greedy replacement keeps tails as small as possible
                // => Smaller tails allow more elements to extend subsequences later
            }
        }
        return tails.size();                 // => Length of tails = LIS length
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lisLength(nums)); // => Output: 4
        // => One LIS is [2, 3, 7, 18] or [2, 5, 7, 18] or [2, 3, 7, 101]
    }
}

#include <stdio.h>
#include <limits.h>

int coin_change(int coins[], int num_coins, int amount) {
    int dp[amount + 1];
    // => dp[i] = minimum coins to make amount i
    // => Initialize all to INT_MAX (impossible) except dp[0]
    for (int i = 0; i <= amount; i++) dp[i] = INT_MAX;
    dp[0] = 0;                                // => Base case: 0 coins needed for amount 0

    for (int i = 1; i <= amount; i++) {       // => Fill dp table from 1 to amount
        for (int c = 0; c < num_coins; c++) {
            if (coins[c] <= i && dp[i - coins[c]] != INT_MAX) {
                // => coin fits: can we do better using this coin?
                int candidate = dp[i - coins[c]] + 1;
                if (candidate < dp[i]) dp[i] = candidate;
                // => +1 for using this coin; dp[i-coin] subproblem already solved
            }
        }
    }
    return dp[amount] != INT_MAX ? dp[amount] : -1;
    // => Return -1 if amount is unreachable with given coins
}

int main(void) {
    int coins1[] = {1, 5, 6, 9};
    printf("%d\n", coin_change(coins1, 4, 11));  // => Output: 2  (coins: 5+6)
    int coins2[] = {2};
    printf("%d\n", coin_change(coins2, 1, 3));   // => Output: -1 (3 unreachable with only even coins)
    int coins3[] = {1, 2, 5};
    printf("%d\n", coin_change(coins3, 3, 11));  // => Output: 3  (coins: 5+5+1)
    return 0;
}

package main

import (
    "fmt"
    "math"
)

func coinChange(coins []int, amount int) int {
    INF := math.MaxInt32                      // => Sentinel for "impossible" states
    dp := make([]int, amount+1)
    // => dp[i] = minimum coins to make amount i
    // => Initialize all to INF (impossible) except dp[0]
    for i := range dp {
        dp[i] = INF
    }
    dp[0] = 0 // => Base case: 0 coins needed for amount 0

    for i := 1; i <= amount; i++ { // => Fill dp table from 1 to amount
        for _, coin := range coins {
            if coin <= i && dp[i-coin] != INF {
                // => coin fits: can we do better using this coin?
                candidate := dp[i-coin] + 1
                if candidate < dp[i] {
                    dp[i] = candidate
                }
                // => +1 for using this coin; dp[i-coin] subproblem already solved
            }
        }
    }
    if dp[amount] != INF {
        return dp[amount]
    }
    return -1 // => Return -1 if amount is unreachable with given coins
}

func main() {
    fmt.Println(coinChange([]int{1, 5, 6, 9}, 11)) // => Output: 2  (coins: 5+6)
    fmt.Println(coinChange([]int{2}, 3))            // => Output: -1 (3 unreachable with only even coins)
    fmt.Println(coinChange([]int{1, 2, 5}, 11))     // => Output: 3  (coins: 5+5+1)
}

def coin_change(coins, amount):
    INF = float('inf')                        # => Sentinel for "impossible" states
    dp = [INF] * (amount + 1)
    # => dp[i] = minimum coins to make amount i
    # => Initialize all to INF (impossible) except dp[0]
    dp[0] = 0                                 # => Base case: 0 coins needed for amount 0

    for i in range(1, amount + 1):           # => Fill dp table from 1 to amount
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                # => coin fits: can we do better using this coin?
                dp[i] = min(dp[i], dp[i - coin] + 1)
                # => +1 for using this coin; dp[i-coin] subproblem already solved

    return dp[amount] if dp[amount] != INF else -1
    # => Return -1 if amount is unreachable with given coins

print(coin_change([1, 5, 6, 9], 11))         # => Output: 2  (coins: 5+6)
print(coin_change([2], 3))                    # => Output: -1 (3 unreachable with only even coins)
print(coin_change([1, 2, 5], 11))             # => Output: 3  (coins: 5+5+1)

import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int INF = Integer.MAX_VALUE;          // => Sentinel for "impossible" states
        int[] dp = new int[amount + 1];
        // => dp[i] = minimum coins to make amount i
        // => Initialize all to INF (impossible) except dp[0]
        Arrays.fill(dp, INF);
        dp[0] = 0;                            // => Base case: 0 coins needed for amount 0

        for (int i = 1; i <= amount; i++) {  // => Fill dp table from 1 to amount
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != INF) {
                    // => coin fits: can we do better using this coin?
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    // => +1 for using this coin; dp[i-coin] subproblem already solved
                }
            }
        }
        return dp[amount] != INF ? dp[amount] : -1;
        // => Return -1 if amount is unreachable with given coins
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 5, 6, 9}, 11)); // => Output: 2  (coins: 5+6)
        System.out.println(coinChange(new int[]{2}, 3));           // => Output: -1 (3 unreachable with only even coins)
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));   // => Output: 3  (coins: 5+5+1)
    }
}

#include <stdio.h>
#include <limits.h>

#define MAXV 100
#define INF INT_MAX

// => Simple min-heap for (distance, vertex) pairs
typedef struct { int dist; int node; } HeapItem;
typedef struct {
    HeapItem data[MAXV * MAXV];
    int size;
} MinHeap;

void heap_push(MinHeap *h, int dist, int node) {
    int i = h->size++;
    h->data[i] = (HeapItem){dist, node};
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h->data[p].dist <= h->data[i].dist) break;
        HeapItem tmp = h->data[p]; h->data[p] = h->data[i]; h->data[i] = tmp;
        i = p;
    }
}

HeapItem heap_pop(MinHeap *h) {
    HeapItem top = h->data[0];
    h->data[0] = h->data[--h->size];
    int i = 0;
    while (1) {
        int l = 2*i+1, r = 2*i+2, m = i;
        if (l < h->size && h->data[l].dist < h->data[m].dist) m = l;
        if (r < h->size && h->data[r].dist < h->data[m].dist) m = r;
        if (m == i) break;
        HeapItem tmp = h->data[i]; h->data[i] = h->data[m]; h->data[m] = tmp;
        i = m;
    }
    return top;
}

// => Adjacency list representation
typedef struct { int weight; int to; } Edge;
Edge adj[MAXV][MAXV];
int adj_size[MAXV];

void dijkstra(int n, int source, int dist[]) {
    // => dist[v] = current best known distance from source to v
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[source] = 0;                         // => Distance from source to itself is 0

    MinHeap heap = {.size = 0};
    heap_push(&heap, 0, source);              // => Min-heap: (distance, node)

    while (heap.size > 0) {
        HeapItem item = heap_pop(&heap);      // => Extract node with minimum distance; O(log V)
        int d = item.dist, u = item.node;
        if (d > dist[u]) continue;            // => Stale entry: a shorter path was already found
        for (int i = 0; i < adj_size[u]; i++) {
            int w = adj[u][i].weight, v = adj[u][i].to;
            int new_dist = dist[u] + w;       // => Candidate distance to v via u
            if (new_dist < dist[v]) {
                dist[v] = new_dist;           // => Found shorter path to v
                heap_push(&heap, new_dist, v);
            }
        }
    }
}

int main(void) {
    // => Map: A=0, B=1, C=2, D=3
    int n = 4;
    for (int i = 0; i < n; i++) adj_size[i] = 0;
    adj[0][adj_size[0]++] = (Edge){1, 1}; // => A -> B weight 1
    adj[0][adj_size[0]++] = (Edge){4, 2}; // => A -> C weight 4
    adj[1][adj_size[1]++] = (Edge){2, 2}; // => B -> C weight 2
    adj[1][adj_size[1]++] = (Edge){5, 3}; // => B -> D weight 5
    adj[2][adj_size[2]++] = (Edge){1, 3}; // => C -> D weight 1

    int dist[MAXV];
    dijkstra(n, 0, dist);
    printf("A=%d B=%d C=%d D=%d\n", dist[0], dist[1], dist[2], dist[3]);
    // => Output: A=0 B=1 C=3 D=4
    return 0;
}