資料結構
網路
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 次觀看
廣告