数据结构
网络
RDBMS
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律研究如何使用 C# 通过自底向上的方法来实现一步步将数字减至 1？
MinimumStepstoOneBottomdownApproach 将整数 n 作为输入。参数 n 包含元素的总数。初始条件检查 n 是否等于 1。如果 n 等于 1，则返回 0。将 op1、op2 和 op3 初始化为最大值。如果 n 模 3 等于 0，则递归调用 MinimumStepstoOneBottomdownApproach 并将它赋值给 op1，如果 n 模 3 等于 0，则递归调用 MinimumStepstoOneBottomdownApproach 并将它赋值给 op2，否则从 n 中减去 1 然后调用 MinimumStepstoOneBottomdownApproach。最后返回 dp 数组中的值
时间复杂度 − O(N)
空间复杂度 − O(N)
示例
public class DynamicProgramming{
public int MinimumStepstoOneBottomdownApproach(int n){
int[] dp = new int[100];
dp[1] = 0;
for (int i = 2; i < n; i++){
int op1 = int.MaxValue, op2 = int.MaxValue, op3 = int.MaxValue;
if (n % 3 == 0){
op1 = dp[i / 3];
}
if (n % 2 == 0){
op2 = dp[i / 2];
}
op3= dp[i -1];
dp[i]= Math.Min(Math.Min(op1, op2), op3) + 1;
}
return dp[n-1];
}
}
static void Main(string[] args){
DynamicProgramming dp = new DynamicProgramming();
Console.WriteLine(dp.MinimumStepstoOneBottomdownApproach(10))
}输出
3
更新于：2021 年 8 月 17 日
171 次观看
广告