322.零钱兑换

/*
 * @lc app=leetcode.cn id=322 lang=typescript
 *
 * [322] 零钱兑换
 */

// @lc code=start
function coinChange(coins: number[], amount: number): number {
	// 初始化DP表
	let dp = Array.from({ length: coins.length + 1 }, () =>
		Array.from({ length: amount + 1 }, () => 0)
	);
	// 设置最大值
	let MAX = amount + 1;
	// 设置dp表首行
	for (let i = 1; i <= amount; i++) {
		dp[0][i] = MAX;
	}

	for (let i = 1; i <= coins.length; i++) {
		for (let j = 1; j <= amount; j++) {
			// 假设当前硬币值大于所需，不选
			if (coins[i - 1] > j) {
				dp[i][j] = dp[i - 1][j];
			} else {
				// 取最小值
				dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
			}
		}
	}

	return dp[coins.length][amount] != MAX ? dp[coins.length][amount] : -1;
}

console.log(coinChange([1, 2, 5], 11));

// @lc code=end