MinimumStepstoOneTopdownApproach รับจำนวนเต็ม n และอาร์เรย์จำนวนเต็มเป็นอินพุต พารามิเตอร์ n มีจำนวนขององค์ประกอบทั้งหมด เงื่อนไขเริ่มต้นตรวจสอบว่า n เท่ากับ 1 หรือไม่ ถ้า n เท่ากับ 1 ให้คืนค่า 0 เริ่มต้น op1,op2 และ op3 เป็นค่าสูงสุด หาก n mod 3 เท่ากับ 0 ให้เรียก MinimumStepstoOneTopdownApproach ซ้ำๆ และกำหนดให้กับ op1 หาก n mod 3 เท่ากับ 0 ให้เรียก MinimumStepstoOneTopdownApproach ซ้ำแล้วซ้ำอีกและกำหนดให้ op2 else ลบ n 1 ด้วย 1 และเรียก MinimumStepstoOneTopdownApproach สุดท้ายเรียก Math.Min เพื่อคำนวณองค์ประกอบขั้นต่ำสามองค์ประกอบและส่งกลับค่าจากอาร์เรย์ dp
ความซับซ้อนของเวลา − O(N)
ความซับซ้อนของอวกาศ − O(N)
ตัวอย่าง
public class DynamicProgramming{
public int MinimumStepstoOneTopdownApproach(int n, int[] dp){
if (n == 1){
return 0;
}
int op1, op2, op3;
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
