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