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