Coin change - bài toán kinh điển về DP
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 thành một số tiền nhất định từ các mệnh giá cho trước (số lượng đồng xu mỗi loại là không giới hạn). Nếu không thể tạo thành số tiền đố, trả về -1
Approach - Bottom up
dp[] với dp[i] là số đồng xu ít nhất để tạo thành số tiền idp = 0 (không cần đồng nào để tạo thành 0)1 đến amount thử từng lại coin, cập nhật dp[i] = min(dp[i], dp[i -coin] + 1 ) nếu i - coin >= 0 dp[amount] nếu bằng Infinity thì trả về -1;Time and space complexity:
Solution - Bottom up dp
1function coinChange(coins: number[], amount: number): number {
2 const dp: number[] = Array(amount + 1).fill(Infinity);
3 dp[0] = 0;
4 for (const coin of coins) {
5 for (let i = coin; i <= amount; i++) {
6 dp[i] = Math.min(dp[i], dp[i - coin] + 1)
7 }
8 }
9
10 return dp[amount] === Infinity ? -1 : dp[amount];
11};