Dynamic Programming: 1D

def rob(nums: list[int]) -> int:
    """Most money you can take from a row of houses without robbing two neighbors."""
    # best(i) = most money from the first i houses
    #         = max(best(i - 1), best(i - 2) + nums[i - 1])
    # Each value reads only the two before it, so keep just those two.
    two_back = 0  # best(i - 2)
    one_back = 0  # best(i - 1)
    for money in nums:
        # Skip this house and keep one_back, or rob it on top of two_back.
        here = max(one_back, two_back + money)
        two_back = one_back
        one_back = here
    return one_back


if __name__ == "__main__":
    print(rob([1, 2, 3, 1]))  # 4
    print(rob([2, 7, 9, 3, 1]))  # 12
    print(rob([2, 1, 1, 2]))  # 4

// Most money you can take from a row of houses without robbing two neighbors.
export function rob(nums: number[]): number {
  // best(i) = most money from the first i houses
  //         = max(best(i - 1), best(i - 2) + nums[i - 1])
  // Each value reads only the two before it, so keep just those two.
  let twoBack = 0; // best(i - 2)
  let oneBack = 0; // best(i - 1)
  for (const money of nums) {
    // Skip this house and keep oneBack, or rob it on top of twoBack.
    const here = Math.max(oneBack, twoBack + money);
    twoBack = oneBack;
    oneBack = here;
  }
  return oneBack;
}

console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([2, 7, 9, 3, 1])); // 12
console.log(rob([2, 1, 1, 2])); // 4

package main

import "fmt"

// rob returns the most money you can take from a row of houses without
// robbing two neighbors.
func rob(nums []int) int {
	// best(i) = most money from the first i houses
	//         = max(best(i - 1), best(i - 2) + nums[i - 1])
	// Each value reads only the two before it, so keep just those two.
	twoBack := 0 // best(i - 2)
	oneBack := 0 // best(i - 1)
	for _, money := range nums {
		// Skip this house and keep oneBack, or rob it on top of twoBack.
		here := max(oneBack, twoBack+money)
		twoBack = oneBack
		oneBack = here
	}
	return oneBack
}

func main() {
	fmt.Println(rob([]int{1, 2, 3, 1}))    // 4
	fmt.Println(rob([]int{2, 7, 9, 3, 1})) // 12
	fmt.Println(rob([]int{2, 1, 1, 2}))    // 4
}

using System;

public class Solution
{
    // Most money you can take from a row of houses without robbing two neighbors.
    public static int Rob(int[] nums)
    {
        // best(i) = most money from the first i houses
        //         = max(best(i - 1), best(i - 2) + nums[i - 1])
        // Each value reads only the two before it, so keep just those two.
        int twoBack = 0; // best(i - 2)
        int oneBack = 0; // best(i - 1)
        foreach (int money in nums)
        {
            // Skip this house and keep oneBack, or rob it on top of twoBack.
            int here = Math.Max(oneBack, twoBack + money);
            twoBack = oneBack;
            oneBack = here;
        }
        return oneBack;
    }

    public static void Main()
    {
        Console.WriteLine(Rob(new[] { 1, 2, 3, 1 })); // 4
        Console.WriteLine(Rob(new[] { 2, 7, 9, 3, 1 })); // 12
        Console.WriteLine(Rob(new[] { 2, 1, 1, 2 })); // 4
    }
}

public class Solution {
    // Most money you can take from a row of houses without robbing two neighbors.
    static int rob(int[] nums) {
        // best(i) = most money from the first i houses
        //         = max(best(i - 1), best(i - 2) + nums[i - 1])
        // Each value reads only the two before it, so keep just those two.
        int twoBack = 0; // best(i - 2)
        int oneBack = 0; // best(i - 1)
        for (int money : nums) {
            // Skip this house and keep oneBack, or rob it on top of twoBack.
            int here = Math.max(oneBack, twoBack + money);
            twoBack = oneBack;
            oneBack = here;
        }
        return oneBack;
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[] {1, 2, 3, 1})); // 4
        System.out.println(rob(new int[] {2, 7, 9, 3, 1})); // 12
        System.out.println(rob(new int[] {2, 1, 1, 2})); // 4
    }
}

def coin_change(coins: list[int], amount: int) -> int:
    """Fewest coins that add up to exactly `amount`, with unlimited coins of each
    denomination, or -1 if no combination of coins can make it."""
    # Stands in for infinity. A real answer never needs more than `amount`
    # coins (all 1s), and unlike a max integer, adding 1 can't overflow.
    unreachable = amount + 1
    dp = [unreachable] * (amount + 1)  # dp[a] = fewest coins that make a
    dp[0] = 0  # Zero coins make zero.
    for a in range(1, amount + 1):
        for coin in coins:
            # If the last coin is `coin`, the rest is the best way to make a - coin.
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return -1 if dp[amount] == unreachable else dp[amount]


if __name__ == "__main__":
    print(coin_change([1, 2, 5], 11))  # 3
    print(coin_change([2], 3))  # -1
    print(coin_change([1], 0))  # 0
    print(coin_change([1, 3, 4], 6))  # 2 (3 + 3, where greedy picks 4 + 1 + 1)

// Fewest coins that add up to exactly `amount`, with unlimited coins of each
// denomination, or -1 if no combination of coins can make it.
export function coinChange(coins: number[], amount: number): number {
  // Stands in for infinity. A real answer never needs more than `amount`
  // coins (all 1s), and unlike a max integer, adding 1 can't overflow.
  const unreachable = amount + 1;
  const dp = new Array<number>(amount + 1).fill(unreachable); // dp[a] = fewest coins that make a
  dp[0] = 0; // Zero coins make zero.
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      // If the last coin is `coin`, the rest is the best way to make a - coin.
      if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === unreachable ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3)); // -1
console.log(coinChange([1], 0)); // 0
console.log(coinChange([1, 3, 4], 6)); // 2 (3 + 3, where greedy picks 4 + 1 + 1)

package main

import "fmt"

// coinChange returns the fewest coins that add up to exactly amount, with
// unlimited coins of each denomination, or -1 if no combination can make it.
func coinChange(coins []int, amount int) int {
	// Stands in for infinity. A real answer never needs more than amount
	// coins (all 1s), and unlike a max integer, adding 1 can't overflow.
	unreachable := amount + 1
	dp := make([]int, amount+1) // dp[a] = fewest coins that make a
	for a := range dp {
		dp[a] = unreachable
	}
	dp[0] = 0 // Zero coins make zero.
	for a := 1; a <= amount; a++ {
		for _, coin := range coins {
			// If the last coin is coin, the rest is the best way to make a - coin.
			if coin <= a {
				dp[a] = min(dp[a], dp[a-coin]+1)
			}
		}
	}
	if dp[amount] == unreachable {
		return -1
	}
	return dp[amount]
}

func main() {
	fmt.Println(coinChange([]int{1, 2, 5}, 11)) // 3
	fmt.Println(coinChange([]int{2}, 3))        // -1
	fmt.Println(coinChange([]int{1}, 0))        // 0
	fmt.Println(coinChange([]int{1, 3, 4}, 6))  // 2 (3 + 3, where greedy picks 4 + 1 + 1)
}

using System;

public class Solution
{
    // Fewest coins that add up to exactly amount, with unlimited coins of each
    // denomination, or -1 if no combination of coins can make it.
    public static int CoinChange(int[] coins, int amount)
    {
        // Stands in for infinity. A real answer never needs more than amount
        // coins (all 1s), and unlike a max integer, adding 1 can't overflow.
        int unreachable = amount + 1;
        var dp = new int[amount + 1]; // dp[a] = fewest coins that make a
        Array.Fill(dp, unreachable);
        dp[0] = 0; // Zero coins make zero.
        for (int a = 1; a <= amount; a++)
        {
            foreach (int coin in coins)
            {
                // If the last coin is coin, the rest is the best way to make a - coin.
                if (coin <= a) dp[a] = Math.Min(dp[a], dp[a - coin] + 1);
            }
        }
        return dp[amount] == unreachable ? -1 : dp[amount];
    }

    public static void Main()
    {
        Console.WriteLine(CoinChange(new[] { 1, 2, 5 }, 11)); // 3
        Console.WriteLine(CoinChange(new[] { 2 }, 3)); // -1
        Console.WriteLine(CoinChange(new[] { 1 }, 0)); // 0
        Console.WriteLine(CoinChange(new[] { 1, 3, 4 }, 6)); // 2 (3 + 3, where greedy picks 4 + 1 + 1)
    }
}

import java.util.Arrays;

public class Solution {
    // Fewest coins that add up to exactly amount, with unlimited coins of each
    // denomination, or -1 if no combination of coins can make it.
    static int coinChange(int[] coins, int amount) {
        // Stands in for infinity. A real answer never needs more than amount
        // coins (all 1s), and unlike a max integer, adding 1 can't overflow.
        int unreachable = amount + 1;
        int[] dp = new int[amount + 1]; // dp[a] = fewest coins that make a
        Arrays.fill(dp, unreachable);
        dp[0] = 0; // Zero coins make zero.
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                // If the last coin is coin, the rest is the best way to make a - coin.
                if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
        return dp[amount] == unreachable ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[] {1, 2, 5}, 11)); // 3
        System.out.println(coinChange(new int[] {2}, 3)); // -1
        System.out.println(coinChange(new int[] {1}, 0)); // 0
        System.out.println(coinChange(new int[] {1, 3, 4}, 6)); // 2 (3 + 3, where greedy picks 4 + 1 + 1)
    }
}