如何使用 C# 使用 topDown 方法实现最小步进?
MinimumStepstoOneTopdownApproach将整数n和整数数组作为输入。参数n包含元素的总数。初始条件检查n是否等于1。如果n等于1,则返回0。将op1、op2和op3初始化为最大值。如果nmod3等于0,则递归调用MinimumStepstoOneTopdownApproach并将其分配给op1,如果nmod3等于0则递归调用MinimumStepstoOneTopdownApproach并将其分配给op2否则将n减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