数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学如何使用 C# 通过自顶向下的方法实现最小化到一步？
MinimumStepstoOneTopdownApproach 以整数 n 和一个整数数组作为输入。参数 n 包含元素的总数。初始条件检查 n 是否等于 1。如果 n 等于 1，则返回 0。初始化 op1、op2 和 op3 为最大值。如果 n mod 3 等于 0，则递归调用 MinimumStepstoOneTopdownApproach 并将其分配给 op1，如果 n mod 3 等于 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
更新时间： 17-Aug-2021
115 次浏览
广告