CoinChangeBottomUpApproach ใช้ 3 พารามิเตอร์เนื่องจากอินพุต n คือจำนวนเงิน อาร์เรย์เหรียญประกอบด้วยจำนวนเหรียญทั้งหมด t มีจำนวนเหรียญทั้งหมด ประกาศอาร์เรย์แบบไดนามิกที่เก็บค่าที่คำนวณไว้ก่อนหน้านี้ วนซ้ำผ่านอาร์เรย์และคำนวณเหรียญขั้นต่ำที่จำเป็นในการคำนวณจำนวน หากคำนวณเสร็จแล้ว ให้นำค่าจากไดนามิกอาร์เรย์
ความซับซ้อนของเวลา - โอ(N)
ความซับซ้อนของอวกาศ - โอ(N)
ตัวอย่าง
public class DynamicProgramming{
public int CoinChangeBottomUpApproach(int n,int[] coins,int t){
int[] dp = new int[100];
for (int i = 1; i < n; i++){
dp[i] = int.MaxValue;
for (int j = 0; j < t; j++){
if (i - coins[j] >= 0){
int subProb = dp[i - coins[j]];
dp[i] = Math.Min(dp[i], subProb + 1);
}
}
}
return dp[n]+1;
}
}
static void Main(string[] args){
DynamicProgramming dp = new DynamicProgramming();
int[] coins = { 1, 7, 10 };
int ss = dp.CoinChangeBottomUpApproach(15, coins, coins.Count());
Console.WriteLine(ss);
} ผลลัพธ์
3
