如何使用 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
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短