เมธอด MinimumStepstoOneBottomdownApproach รับพารามิเตอร์ n (จำนวนเต็ม) ตรวจสอบเงื่อนไขเริ่มต้น: หาก n == 1 คืนค่า 0 เริ่มต้น op1, op2, op3 เป็นค่าสูงสุด หาก n หาร 3 ลงตัว เรียกเมธอดซ้ำกับ n/3 และกำหนดให้ op1 หาก n หาร 2 ลงตัว เรียกซ้ำกับ n/2 ให้ op2 ไม่เช่นนั้นลบ n ลง 1 เรียกซ้ำกับ n-1 ให้ op3 สุดท้ายคืนค่าจาก dp array
Time Complexity: O(N)
Space Complexity: O(N)
ตัวอย่างโค้ด
public class DynamicProgramming
{
public int MinimumStepstoOneBottomdownApproach(int n)
{
int[] dp = new int[100];
dp[1] = 0;
for (int i = 2; i <= n; i++)
{
int op1 = int.MaxValue, op2 = int.MaxValue, op3 = int.MaxValue;
if (i % 3 == 0)
{
op1 = dp[i / 3];
}
if (i % 2 == 0)
{
op2 = dp[i / 2];
}
op3 = dp[i - 1];
dp[i] = Math.Min(Math.Min(op1, op2), op3) + 1;
}
return dp[n];
}
}
static void Main(string[] args)
{
DynamicProgramming dp = new DynamicProgramming();
Console.WriteLine(dp.MinimumStepstoOneBottomdownApproach(10));
}ผลลัพธ์
3
หมายเหตุ: โค้ดต้นฉบับมีข้อผิดพลาดตรงเงื่อนไข if (n % 3 == 0) ควรเป็น i % 3 == 0 และลูปควรเป็น i <= n โค้ดข้างต้นแก้ไขให้ถูกต้องแล้ว
