Swift算法實例分析之動態規劃
今天要講的動態規劃，其面對的問題通常是無法一蹴而就，需要把復雜的問題分解成簡單具體的小問題，然后通過求解簡單問題，去推出復雜問題的最終解。
形象的理解就是為了推倒一系列紙牌中的第100張紙牌，那么我們就要先推倒第1張，再依靠多米諾骨牌效應，去推倒第100張。
實例講解
斐波拉契數列是這樣一個數列：1， 1， 2， 3， 5， 8， 。。. 除了第一個和第二個數字為1以外，其他數字都為之前兩個數字之和。現在要求第100個數字是多少。
這道題目乍一看是一個數學題，那么要求第100個數字，很簡單，一個個數字算下去就是了。假設F（n）表示第n個斐波拉契數列的數字，那么我們易得公式F（n） = F（n - 1） + F（n - 2），n 》= 2，下面就是體力活。當然這道題轉化成代碼也不是很難，最粗暴的解法如下：
func Fib（） -》 Int {
var prev = 0
var curr = 1
for _ in 1 。。《 100 {
var temp = curr
curr = prev + curr
prev = temp
}
return curr
}
用動態規劃怎么寫呢？首先要明白動態規劃有以下幾個專有名詞：
1. 初始狀態，即此問題的最簡單子問題的解。在斐波拉契數列里，最簡單的問題是，一開始給定的第一個數和第二個數是幾？自然我們可以得出是1
2. 狀態轉移方程，即第n個問題的解和之前的 n - m 個問題解的關系。在這道題目里，我們已經有了狀態轉移方程F（n） = F（n - 1） + F（n - 2）
所以這題要求F（100），那我們只要知道F（99）和F（98）就行了；想知道F（99），我們只要知道F（98）和F（97）就行了；想要知道F（98），我們需要知道F（97）和F（96）。。。，以此類推，我們最后只要知道F（2）和F（1）的值，就可以推出F（100）。而F（2）和F（1）正是我們所謂的初始狀態，即 F（2） = 1，F（1） =1。所以代碼如下：
func Fib（n： Int） -》 Int {
// 定義初始狀態
guard n 》 0 else {
return 0
}
if n == 1 || n == 2 {
return 1
}
// 調用狀態轉移方程
return Fib（n - 1） + Fib（n - 2）
}
print（Fib（100））
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%
下載地址
Swift算法實例分析之動態規劃下載
相關電子資料下載
- 拿下國家級信創認證！中科馭數KPU SWIFT-2200N成為國內首款滿足金融業嚴苛要求的 163
- 中科馭數基于DPU的思威SWIFT系列智能網卡與統信軟件產品完成適配 176
- 如何使用Swift提高代碼質量 126
- 積木易搭Magic Swift Plus為雕刻工藝品精雕復刻提供三維數字化解決方案 274
- 詞法分析-Antlr-1 235
- Kotlin 1.8.0發布，改進性能和Swift的互操作性 1044
- Swift 2023：強調并發、泛型和C++互操作性，開發Swift解析器 300
- 彩色套件創建全彩3D模型MagicSwiftPlus僅千元級 432
- Swift的使用體驗與生態發展之路 981
- 如何加速apply函數600倍的技巧 627