#45. Climbing Stairs - vezi si aici
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
class Solution {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}
Integer[] cache = new Integer[n+1];
return check(n, 0, cache);
}
private int check(int steps, int ways, Integer[] cache) {
if (steps < 0) {
return 0;
}
if (steps == 0) {
return 1;
}
//return check(steps - 1, ways + 1, cache) + check(steps - 2, ways + 1, cache);
cache[steps] = 0;
if (steps >= 1) {
if (cache[steps-1] == null) {
cache[steps-1] = check(steps - 1, ways + 1, cache);
}
cache[steps] += cache[steps-1];
}
if (steps >= 2) {
if (cache[steps-2] == null) {
cache[steps-2] = check(steps - 2, ways + 1, cache);
}
cache[steps] += cache[steps-2];
}
return cache[steps];
}
}
#46. Coin Change
You are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
// solutie greedy & backtracking care depaseste timpul alocat
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
List<Integer> sortedCoins = Arrays.stream(coins).boxed().collect(Collectors.toList());
Collections.sort(sortedCoins, Collections.reverseOrder());
return change(amount, sortedCoins, 0);
}
private int change(int amount, List<Integer> coins, int coinsToHere) {
if (coins.isEmpty()) {
return -1; // impossible to satisfy
}
if (coins.get(0) > amount) {
return change(amount, coins.subList(1, coins.size()), coinsToHere); // search with lower value coins
}
int maxFullCoins = amount / coins.get(0);
int rest = amount % coins.get(0);
if (rest == 0) {
return maxFullCoins + coinsToHere; // exact match
}
int minSoFar = Integer.MAX_VALUE;
boolean found = false;
for (int i=maxFullCoins; i>=0; i--) {
int coinsNeeded = change(rest, coins.subList(1, coins.size()), i + coinsToHere);
if (coinsNeeded != -1 && minSoFar > coinsNeeded) { // if successful and more optimal change
minSoFar = coinsNeeded;
found = true;
}
rest += coins.get(0);
}
return found ? minSoFar : -1;
}
}
// solutie mai buna (programare dinamica bottom-up) dar tot depaseste timpul pt date de intrare mari
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
List<Integer> sortedCoins = Arrays.stream(coins).boxed().collect(Collectors.toList());
Collections.sort(sortedCoins, Collections.reverseOrder());
// idea: make an array of all amounts <= amount
// such that array[k] = optimal number of coins to compose amount k
// then derive array[amount] by looking back and taking the min sum
// array[i] + array[j] such that i + j = k
Integer changes[] = getInitialChanges(sortedCoins, amount);
changes = refine(changes);
return changes[amount] != null ? changes[amount] : -1;
}
private Integer[] getInitialChanges(List<Integer> sortedCoins, int amount) {
Integer changes[] = new Integer[amount + 1];
changes[0] = 0;
for (int coin : sortedCoins) {
int maxCoins = amount / coin; // how many coins can fill <= amount
for (int i=1; i<=maxCoins; i++) {
if (changes[coin * i] == null) { // if not null, amount was filled with larger & less coins
changes[coin * i] = i;
}
}
}
return changes;
}
private Integer[] refine(Integer[] changes) {
for (int i=1; i<changes.length; i++) {
for (int j=i-1; j>=i/2; j--) {
if (changes[j] == null || changes[i-j] == null) {
continue;
}
int prevSum = changes[j] + changes[i-j]; // j + i - j = i (current amount)
changes[i] = changes[i] == null ? prevSum : Math.min(changes[i], prevSum);
}
}
return changes;
}
}
// solutie acceptabila
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
Integer changes[] = new Integer[amount + 1];
changes[0] = 0;
for (int i=1; i<changes.length; i++) {
changes[i] = amount + 1; // something greater than amount pieces of 1's
}
for (int i=1; i<changes.length; i++) { // building the table bottom-up for amounts from 1 to amount
for (int j=0; j<coins.length; j++) { // consider taking this coin to compose amount i
if (coins[j] <= i) { // if current coin can fit current amount
int restAmount = i - coins[j];
// keep as is or update taking current coin + what else needed to fill restAmount
changes[i] = Math.min(changes[i], changes[restAmount] + 1); // 1 for taking coins[j]
// will update only if changes[restAmount] is known & optimal enough
}
}
}
return changes[amount] == amount + 1 ? -1 : changes[amount];
}
}
