# Coin Change

You are given an integer array 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.

You may assume that you have an infinite number of each kind of coin.

```
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
numCoins = len(coins)
# Values in this array equal the number of coins needed to achieve the cost of the index
minCoins = [amount + 1] * (amount + 1)
minCoins[0] = 0
# Loop through every needed amount
for i in range(amount + 1):
# Loop through every coin value
for coin in coins:
# Check that the coin is not bigger than the current amount
if coin <= i:
# minCoins[i]: number of coins needed to make amount i
# minCoins[i-coin]: number of coins needed to make the amount before adding
# the current coin to it (+1 to add the current coin)
minCoins[i] = min(minCoins[i], minCoins[i-coin] + 1)
# Check if any combination of coins was found to create the amount
if minCoins[amount] == amount + 1:
return -1
# Return the optimal number of coins to create the amount
return minCoins[amount]
```

## Related Problems

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.

There is a robot on an m x n grid. The robot is initially located at the **top-left corner** (i.e., grid[0][0]). The robot tries to move to the **bottom-right corner** (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if **two directly-linked houses were broken into on the same night**.

Given the root of the binary tree, return *the maximum amount of money the thief can rob ***without alerting the police**.