322. Coin Change
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm số lượng đồng xu ít nhất để tạo ra một số tiền nhất định, với mỗi loại đồng xu có thể sử dụng không giới hạn số lượng. Nếu không thể tạo ra số tiền đó, return về -1
Approach
amount là tối thiểu của số đồng xu để tạo thành các số tiền nhỏ hơn amount - coin cộng thêm 1 với mỗi loại coindp trong đó dp[i] là số đồng xu tối thiểu để tạo thành số tiền i . Khởi tạo dp = 0 (không cần đồng nào để tạo thành 0), các giá trị còn lại là vô cùng lớn (Infinity)dp[i] = min(dp[i], dp[i - coin] + 1) cho mọi i từ coin → amountDP là một mảng dùng để lưu kết quả tối ưu của các bài toán con - cụ thể trong bài Coin Change, mỗi phần tử dp[i] lưu số lượng đồng xu ít nhất cần dùng để tạo thành số tiền đúng bằng i
Giải thích chi tiết
dp[i] chính là bài toán con: “Số đồng xu ít nhất để đổi ra số tiền i ”dp=0 (vì không cần đồng xu nào để tạo ra 0 đồng) và các giá trị còn lại là vô cùng lớn (Infinity) vì chưa biết cách đổidp[i] sao cho nó luôn là nhỏ nhất (tối ưu nhất) dựa tên các bài toán con trước đóTime and space complexity
Solution
1function coinChange(coins: number[], amount: number): number {
2 const dp = Array(amount + 1).fill(Infinity);
3 dp[0] = 0
4 for (const coin of coins) {
5 for (let i = coin; i <= amount; i++) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
6 }
7 return dp[amount] === Infinity ? -1 : dp[amount]
8};dp = 0dp[amount] vẫn là Infinity, nghĩa là không thể tạo thành amount với các loại coin đã cho, return về -1. Ngược lại, return về dp[amount] dp[i - coin] + 1 ?coin , nếu bạn đã biết cách tạo ra số tiền i - coin với số đồng xu ít nhất là dp[i - coin] thì chỉ cần thêm 1 đồng coin nữa sẽ ra được số tiền i i bằng cách dùng thêm đồng coin này là dp[i - coin] + 1