518. Coin change II

518_solution1_tab.c

#include <stdlib.h>

int change(int amount, int *coins, int coinsSize) {
  int n = coinsSize, w = amount + 1;
  // dp[i * w + x]; unsigned so intermediate overflow wraps instead of being UB
  unsigned long long *dp = calloc((n + 1) * w, sizeof(unsigned long long));
  for (int i = 0; i <= n; i++)
    dp[i * w] = 1; // one way to make 0: use nothing

  for (int i = 1; i <= n; i++) {
    for (int x = 1; x <= amount; x++) {
      dp[i * w + x] = dp[(i - 1) * w + x]; // skip coin i
      if (coins[i - 1] <= x)
        dp[i * w + x] += dp[i * w + (x - coins[i - 1])]; // take coin i (same row)
    }
  }
  int res = (int)dp[n * w + amount];
  free(dp);
  return res;
}

518_solution2_memo.c

#include <stdlib.h>

static int f(int i, int x, int *coins, int n, int w, unsigned *dp) {
  if (x == 0)
    return 1; // made the amount
  if (i == n)
    return 0; // out of coins
  if (dp[i * w + x] != (unsigned)-1)
    return dp[i * w + x];

  unsigned skip = f(i + 1, x, coins, n, w, dp); // never use coin i again
  unsigned take = 0;
  if (coins[i] <= x)
    take = f(i, x - coins[i], coins, n, w,
             dp); // use coin i, stay at i (reuse allowed)

  // unsigned so intermediate overflow wraps instead of being UB
  return dp[i * w + x] = skip + take;
}

int change(int amount, int *coins, int coinsSize) {
  int w = amount + 1;
  unsigned *dp = malloc(coinsSize * w * sizeof(unsigned)); // dp[i * w + x]
  for (int k = 0; k < coinsSize * w; k++)
    dp[k] = (unsigned)-1;
  int res = f(0, amount, coins, coinsSize, w, dp);
  free(dp);
  return res;
}

518_solution3_opt.c

#include <stdlib.h>

int change(int amount, int *coins, int coinsSize) {
  // unsigned so intermediate overflow wraps instead of being UB
  unsigned long long *dp = calloc(amount + 1, sizeof(unsigned long long));
  dp[0] = 1;
  for (int k = 0; k < coinsSize; k++) {
    int c = coins[k];
    for (int x = c; x <= amount; x++)
      dp[x] += dp[x - c];
  }
  int res = (int)dp[amount];
  free(dp);
  return res;
}

518_solution1_tab.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int change(int amount, vector<int> &coins) {
    int n = coins.size();
    vector<vector<unsigned long long>> dp(
        n + 1, vector<unsigned long long>(amount + 1, 0));
    for (int i = 0; i <= n; i++)
      dp[i][0] = 1; // one way to make 0: use nothing

    for (int i = 1; i <= n; i++) {
      for (int x = 1; x <= amount; x++) {
        dp[i][x] = dp[i - 1][x]; // skip coin i
        if (coins[i - 1] <= x)
          dp[i][x] += dp[i][x - coins[i - 1]]; // take coin i (same row)
      }
    }
    return (int)dp[n][amount];
  }
};

518_solution2_memo.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int f(int i, int x, vector<int> &coins, vector<vector<int>> &dp) {
    if (x == 0)
      return 1; // made the amount
    if (i == coins.size())
      return 0; // out of coins
    if (dp[i][x] != -1)
      return dp[i][x];

    int skip = f(i + 1, x, coins, dp); // never use coin i again
    int take = 0;
    if (coins[i] <= x)
      take = f(i, x - coins[i], coins,
               dp); // use coin i, stay at i (reuse allowed)

    return dp[i][x] = skip + take;
  }

  int change(int amount, vector<int> &coins) {
    vector<vector<int>> dp(coins.size(), vector<int>(amount + 1, -1));
    return f(0, amount, coins, dp);
  }
};

518_solution3_opt.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int change(int amount, vector<int> &coins) {
    vector<unsigned long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
      for (int x = c; x <= amount; x++)
        dp[x] += dp[x - c];
    return (int)dp[amount];
  }
};

518_solution1_tab.go

package dp

func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([][]uint64, n+1)
    for i := range dp {
        dp[i] = make([]uint64, amount+1)
        dp[i][0] = 1 // one way to make 0: use nothing
    }

    for i := 1; i <= n; i++ {
        for x := 1; x <= amount; x++ {
            dp[i][x] = dp[i-1][x] // skip coin i
            if coins[i-1] <= x {
                dp[i][x] += dp[i][x-coins[i-1]] // take coin i (same row)
            }
        }
    }
    return int(int32(dp[n][amount]))
}

518_solution2_memo.go

package dp

func change(amount int, coins []int) int {
    dp := make([][]int, len(coins))
    for i := range dp {
        dp[i] = make([]int, amount+1)
        for x := range dp[i] {
            dp[i][x] = -1
        }
    }

    var f func(i, x int) int
    f = func(i, x int) int {
        if x == 0 {
            return 1 // made the amount
        }
        if i == len(coins) {
            return 0 // out of coins
        }
        if dp[i][x] != -1 {
            return dp[i][x]
        }

        skip := f(i+1, x) // never use coin i again
        take := 0
        if coins[i] <= x {
            take = f(i, x-coins[i]) // use coin i, stay at i (reuse allowed)
        }

        dp[i][x] = skip + take
        return dp[i][x]
    }

    return f(0, amount)
}

518_solution3_opt.go

package dp

func change(amount int, coins []int) int {
    dp := make([]uint64, amount+1)
    dp[0] = 1
    for _, c := range coins {
        for x := c; x <= amount; x++ {
            dp[x] += dp[x-c]
        }
    }
    return int(int32(dp[amount]))
}

518_solution1_tab.java

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        long[][] dp = new long[n + 1][amount + 1];
        for (int i = 0; i <= n; i++)
            dp[i][0] = 1; // one way to make 0: use nothing

        for (int i = 1; i <= n; i++) {
            for (int x = 1; x <= amount; x++) {
                dp[i][x] = dp[i - 1][x]; // skip coin i
                if (coins[i - 1] <= x)
                    dp[i][x] += dp[i][x - coins[i - 1]]; // take coin i (same row)
            }
        }
        return (int) dp[n][amount];
    }
}

518_solution2_memo.java

import java.util.Arrays;

class Solution {
    private int f(int i, int x, int[] coins, int[][] dp) {
        if (x == 0)
            return 1; // made the amount
        if (i == coins.length)
            return 0; // out of coins
        if (dp[i][x] != -1)
            return dp[i][x];

        int skip = f(i + 1, x, coins, dp); // never use coin i again
        int take = 0;
        if (coins[i] <= x)
            take = f(i, x - coins[i], coins, dp); // use coin i, stay at i (reuse allowed)

        return dp[i][x] = skip + take;
    }

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount + 1];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return f(0, amount, coins, dp);
    }
}

518_solution3_opt.java

class Solution {
    public int change(int amount, int[] coins) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int c : coins)
            for (int x = c; x <= amount; x++)
                dp[x] += dp[x - c];
        return (int) dp[amount];
    }
}

518_solution1_tab.js

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  const n = coins.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(0));
  for (let i = 0; i <= n; i++) dp[i][0] = 1; // one way to make 0: use nothing

  for (let i = 1; i <= n; i++) {
    for (let x = 1; x <= amount; x++) {
      dp[i][x] = dp[i - 1][x]; // skip coin i
      if (coins[i - 1] <= x) dp[i][x] += dp[i][x - coins[i - 1]]; // take coin i (same row)
    }
  }
  return dp[n][amount];
};

518_solution2_memo.js

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  const dp = Array.from({ length: coins.length }, () => new Array(amount + 1).fill(-1));

  const f = (i, x) => {
    if (x === 0) return 1; // made the amount
    if (i === coins.length) return 0; // out of coins
    if (dp[i][x] !== -1) return dp[i][x];

    const skip = f(i + 1, x); // never use coin i again
    let take = 0;
    if (coins[i] <= x) take = f(i, x - coins[i]); // use coin i, stay at i (reuse allowed)

    return (dp[i][x] = skip + take);
  };

  return f(0, amount);
};

518_solution3_opt.js

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins)
    for (let x = c; x <= amount; x++) dp[x] += dp[x - c];
  return dp[amount];
};

518_solution1_tab.py

from typing import List


class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 1  # one way to make 0: use nothing

        for i in range(1, n + 1):
            for x in range(1, amount + 1):
                dp[i][x] = dp[i - 1][x]  # skip coin i
                if coins[i - 1] <= x:
                    dp[i][x] += dp[i][x - coins[i - 1]]  # take coin i (same row)
        return dp[n][amount]

518_solution2_memo.py

import sys
from typing import List


class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        sys.setrecursionlimit(max(1000, 2 * (len(coins) + amount) + 100))  # deep recursion
        dp = [[-1] * (amount + 1) for _ in range(len(coins))]

        def f(i: int, x: int) -> int:
            if x == 0:
                return 1  # made the amount
            if i == len(coins):
                return 0  # out of coins
            if dp[i][x] != -1:
                return dp[i][x]

            skip = f(i + 1, x)  # never use coin i again
            take = 0
            if coins[i] <= x:
                take = f(i, x - coins[i])  # use coin i, stay at i (reuse allowed)

            dp[i][x] = skip + take
            return dp[i][x]

        return f(0, amount)

518_solution3_opt.py

from typing import List


class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for c in coins:
            for x in range(c, amount + 1):
                dp[x] += dp[x - c]
        return dp[amount]

518_solution1_tab.rs

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let (n, amount) = (coins.len(), amount as usize);
        let mut dp = vec![vec![0u64; amount + 1]; n + 1];
        for i in 0..=n {
            dp[i][0] = 1; // one way to make 0: use nothing
        }

        for i in 1..=n {
            let c = coins[i - 1] as usize;
            for x in 1..=amount {
                dp[i][x] = dp[i - 1][x]; // skip coin i
                if c <= x {
                    // take coin i (same row); wrapping: intermediates may overflow
                    dp[i][x] = dp[i][x].wrapping_add(dp[i][x - c]);
                }
            }
        }
        dp[n][amount] as i32
    }
}

518_solution2_memo.rs

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let mut dp = vec![vec![-1i64; amount as usize + 1]; coins.len()];
        Self::f(0, amount as usize, &coins, &mut dp) as i32
    }

    fn f(i: usize, x: usize, coins: &[i32], dp: &mut Vec<Vec<i64>>) -> i64 {
        if x == 0 {
            return 1; // made the amount
        }
        if i == coins.len() {
            return 0; // out of coins
        }
        if dp[i][x] != -1 {
            return dp[i][x];
        }

        let skip = Self::f(i + 1, x, coins, dp); // never use coin i again
        let c = coins[i] as usize;
        let take = if c <= x {
            Self::f(i, x - c, coins, dp) // use coin i, stay at i (reuse allowed)
        } else {
            0
        };

        // keep within u32 range so -1 stays a free sentinel and nothing overflows
        dp[i][x] = (skip + take) & 0xFFFF_FFFF;
        dp[i][x]
    }
}

518_solution3_opt.rs

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let amount = amount as usize;
        let mut dp = vec![0u64; amount + 1];
        dp[0] = 1;
        for &c in &coins {
            for x in c as usize..=amount {
                // wrapping: intermediates may overflow
                dp[x] = dp[x].wrapping_add(dp[x - c as usize]);
            }
        }
        dp[amount] as i32
    }
}