322. Coin change

#include <stdlib.h>

int coinChange(int *coins, int coinsSize, int amount) {
  int INF = amount + 1;
  int *dp = malloc((amount + 1) * sizeof(int));
  dp[0] = 0;
  for (int x = 1; x <= amount; x++)
    dp[x] = INF;

  for (int x = 1; x <= amount; x++) {
    for (int k = 0; k < coinsSize; k++) {
      int c = coins[k];
      if (c <= x && dp[x - c] != INF && dp[x - c] + 1 < dp[x]) {
        dp[x] = dp[x - c] + 1;
      }
    }
  }
  int res = dp[amount] == INF ? -1 : dp[amount];
  free(dp);
  return res;
}

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int coinChange(vector<int> &coins, int amount) {
    int INF = amount + 1;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;

    for (int x = 1; x <= amount; x++) {
      for (int c : coins) {
        if (c <= x && dp[x - c] != INF) {
          dp[x] = min(dp[x], dp[x - c] + 1);
        }
      }
    }
    return dp[amount] == INF ? -1 : dp[amount];
  }
};

package dp

func coinChange(coins []int, amount int) int {
    INF := amount + 1
    dp := make([]int, amount+1)
    for x := 1; x <= amount; x++ {
        dp[x] = INF
    }

    for x := 1; x <= amount; x++ {
        for _, c := range coins {
            if c <= x && dp[x-c] != INF {
                dp[x] = min(dp[x], dp[x-c]+1)
            }
        }
    }
    if dp[amount] == INF {
        return -1
    }
    return dp[amount]
}

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int x = 1; x <= amount; x++) {
            for (int c : coins) {
                if (c <= x && dp[x - c] != INF) {
                    dp[x] = Math.min(dp[x], dp[x - c] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;

  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x && dp[x - c] !== INF) {
        dp[x] = Math.min(dp[x], dp[x - c] + 1);
      }
    }
  }
  return dp[amount] === INF ? -1 : dp[amount];
};

from typing import List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1
        dp = [INF] * (amount + 1)
        dp[0] = 0

        for x in range(1, amount + 1):
            for c in coins:
                if c <= x and dp[x - c] != INF:
                    dp[x] = min(dp[x], dp[x - c] + 1)
        return -1 if dp[amount] == INF else dp[amount]

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let amount = amount as usize;
        let inf = amount as i32 + 1;
        let mut dp = vec![inf; amount + 1];
        dp[0] = 0;

        for x in 1..=amount {
            for &c in &coins {
                let c = c as usize;
                if c <= x && dp[x - c] != inf {
                    dp[x] = dp[x].min(dp[x - c] + 1);
                }
            }
        }
        if dp[amount] == inf { -1 } else { dp[amount] }
    }
}