Python 學習演算法－動態規劃（Dynammic Programming）
閱讀時間約 0 分鐘
動態規劃(Dynamic Programming)的基本思想是將複雜的問題分解為較小的子問題，並找到這些子問題的關聯性，通過這些子問題的解，我們可以避免重複計算，從而節省計算資源。這種過程稱為「記憶化(Memoization)」，通常使用數組或字典來實現，以在後續的計算中快速查找和重用中間結果。
範例－費波那契數
F(n) = 1 if n ≤ 1
F(n) = F(n-1) + F(n-2) else n
若要以Python撰寫計算費波那契數，最簡單的寫法是直接根據方程式組寫成遞迴(Recursion)。
def fib(n):
return 1 if n <= 1 else fib(n - 1) + fib(n - 2)
這種寫法非常直觀，然而在實務上，我們會發現這個遞迴會重複計算我們已經計算過的答案，以fib(4)為例：
fib(4)
可以發現 fib(2) 被重複計算了兩次，當 n > 20 後，被重複計算的節點數量會非常可觀，為了改善這項問題，我們可以使用一個陣列來儲存算過的答案，這種技巧稱為「記憶化(Memoization)」，這邊我們使用 dp 這個陣列來儲存， dp[i] 代表 fib(i) 的答案：
def fib(n):
dp = [None for _ in range(n + 1)]
dp[0] = dp[1] = 1
def solve(i):
if not dp[i]:
dp[i] = fib(i - 1) + fib(i - 2)
return dp[i]
return solve(n)
一樣以 fib(4) 為例：
fib(4)
可以發現因為fib(2)已經被算過了，我們就不用再下去遞迴了。
目前的做法，我們都是從 n 開始，一路向下遞迴，直到有答案在返回，這種作法稱為Top-Down，那是否有方法從 0 開始，一路算到 n 呢？答案是有的，我們可以利用迴圈，從 0 一路往上開始製表(Tabulation)，這種方法稱為Bottom-Up。
def fib(n):
dp = defaultdict(int)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
當我們使用Bottom-Up時，可以發現，當迴圈跑到 i 時，我們只會使用到 i - 1 與 i - 2 ， i - 3 以下則不會使用到了，也因此，我們只需要兩個變數，紀錄 i - 1 與 i - 2，並不對更新，並不用全部存起來，這時，我們可以使用另一個技巧－空間管理(Space Optimization)。
def fib(n):
curr = prev = prevv = 1
for i in range(2, n + 1):
curr = prev + prevv
prev, prevv = curr, prev
return curr
13會員
4Content count
留言0
查看全部
你可能也想看
重點摘要：
1.9 月降息 2 碼、進一步暗示年內還有 50 bp 降息
2.SEP 上修失業率預期，但快速的降息速率將有助失業率觸頂
3.未來幾個月經濟數據將繼續轉弱，經濟復甦的時點或是 1Q25 季底附近
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎？
新版式整體視覺上「更加凸顯圖片」，為了搭配這次的更新，我們推出首次貼文策展 ❤️
使用貼文功能並完成這次的指定任務，還有機會獲得富士即可拍，讓你的美好回憶都可以用即可拍珍藏！
生成器表達式是 Python 中一種更簡潔的語法，專門用來創建生成器。它的語法與列表生成式類似，但將列表生成式中的方括號 [] 替換為小括號 ()。生成器表達式與生成器函數類似，具有「惰性評估」的特性，因此它只在需要時才生成元素，從而節省記憶體。
生成器的「惰性評估」（也叫延遲求值）指的是生成器不
一、基本算術運算符號
加法：+
減法：-
乘法：*
除法：/（返回浮點數）
a = 1
b = 2
print( a + b ) # 加法 輸出：3
print( a - b ) # 減法 輸出：-1
print( a * b ) # 乘法 輸出：2
print( a / b ) #
就如同標題一樣，input的作用就是從使用者那裡獲取輸入，直到使用者輸入一段文本並按下 ENTER 鍵。
然而用戶輸入的數據（文本）都將作為字串被返回，並存儲在變數中。
接著我們舉個例，比如說我們在一段數據中需要獲取使用者的名稱，範例如下：
name = input("請輸入你的名字：") #
在 Python 中，print( ) 函數用於將結果輸出到螢幕上。當你嘗試將不同資料型別（例如字串和數字）混合在一起輸出時，print( )函數無法直接處理這些不同型別的資料，因此你需要先將它們轉換為相同的資料型別。通常，這意味著需要將數字轉換為字串型別，以便與其他字串一同輸出。
雖然我們也可以
bool（boolean）布林值：
布林值在程式設計和演算法中扮演著至關重要的角色。它主要用於決策過程中，幫助程序根據不同的條件做出不同的處理。
在布林值中只有兩種可能的值，True（為真） 跟 False（為假），用來判斷結果。
布林值中我們使用 if 的條件語句，在我們設置一些條件的時候，
我們介紹了字串和列表的索引和切片操作。索引使用方括號[]來選擇字串或列表中的特定元素，並可以使用正向索引（從0開始）或反向索引（從最後一個元素為-1）來訪問元素。切片使用方括號[]和冒號:來選擇字串或列表中的一段子序列，指定起始位置和結束位置（不包含），並可以使用步長來控制間隔。
本篇文章介紹了在Python中的錯誤處理機制。錯誤處理在程式設計中是一個重要環節，能夠有效處理可能發生的錯誤。示範了如何捕捉錯誤並根據不同錯誤類型進行處理或提示。此外，還介紹了指定特定錯誤類型和捕捉所有錯誤的方法。透過學習這些錯誤處理的技巧，讀者可以更好地避免程式崩潰，提供友善的使用者體驗。
我們將探索函式的定義和調用，這是程式設計中非常重要且強大的概念，它可以將大型程式切割成小的、可重複使用的函式。讓我們一起來了解吧！函式的定義、呼叫和返回值是學習函式的核心。
我們探討了while迴圈的使用，不同於for迴圈，while迴圈以條件式判斷為基礎，而非限定重複次數。我們介紹了使用break語句強制結束迴圈，以及使用continue語句跳過特定程式碼並返回迴圈開頭，同時，我們提及了無窮迴圈的概念，強調了在迴圈中必須更改迴圈變數的值，以避免無窮迴圈的發生。
迴圈對象可以是列表或範圍，透過定義重複動作的內容，我們可以在迴圈中執行指定次數的操作。利用range函數，我們可以自訂重複執行的次數。同時，我們也介紹了break和continue的使用，以及巢狀迴圈的特性。
重點摘要：
1.9 月降息 2 碼、進一步暗示年內還有 50 bp 降息
2.SEP 上修失業率預期，但快速的降息速率將有助失業率觸頂
3.未來幾個月經濟數據將繼續轉弱，經濟復甦的時點或是 1Q25 季底附近
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎？
新版式整體視覺上「更加凸顯圖片」，為了搭配這次的更新，我們推出首次貼文策展 ❤️
使用貼文功能並完成這次的指定任務，還有機會獲得富士即可拍，讓你的美好回憶都可以用即可拍珍藏！
生成器表達式是 Python 中一種更簡潔的語法，專門用來創建生成器。它的語法與列表生成式類似，但將列表生成式中的方括號 [] 替換為小括號 ()。生成器表達式與生成器函數類似，具有「惰性評估」的特性，因此它只在需要時才生成元素，從而節省記憶體。
生成器的「惰性評估」（也叫延遲求值）指的是生成器不
一、基本算術運算符號
加法：+
減法：-
乘法：*
除法：/（返回浮點數）
a = 1
b = 2
print( a + b ) # 加法 輸出：3
print( a - b ) # 減法 輸出：-1
print( a * b ) # 乘法 輸出：2
print( a / b ) #
就如同標題一樣，input的作用就是從使用者那裡獲取輸入，直到使用者輸入一段文本並按下 ENTER 鍵。
然而用戶輸入的數據（文本）都將作為字串被返回，並存儲在變數中。
接著我們舉個例，比如說我們在一段數據中需要獲取使用者的名稱，範例如下：
name = input("請輸入你的名字：") #
在 Python 中，print( ) 函數用於將結果輸出到螢幕上。當你嘗試將不同資料型別（例如字串和數字）混合在一起輸出時，print( )函數無法直接處理這些不同型別的資料，因此你需要先將它們轉換為相同的資料型別。通常，這意味著需要將數字轉換為字串型別，以便與其他字串一同輸出。
雖然我們也可以
bool（boolean）布林值：
布林值在程式設計和演算法中扮演著至關重要的角色。它主要用於決策過程中，幫助程序根據不同的條件做出不同的處理。
在布林值中只有兩種可能的值，True（為真） 跟 False（為假），用來判斷結果。
布林值中我們使用 if 的條件語句，在我們設置一些條件的時候，
我們介紹了字串和列表的索引和切片操作。索引使用方括號[]來選擇字串或列表中的特定元素，並可以使用正向索引（從0開始）或反向索引（從最後一個元素為-1）來訪問元素。切片使用方括號[]和冒號:來選擇字串或列表中的一段子序列，指定起始位置和結束位置（不包含），並可以使用步長來控制間隔。
本篇文章介紹了在Python中的錯誤處理機制。錯誤處理在程式設計中是一個重要環節，能夠有效處理可能發生的錯誤。示範了如何捕捉錯誤並根據不同錯誤類型進行處理或提示。此外，還介紹了指定特定錯誤類型和捕捉所有錯誤的方法。透過學習這些錯誤處理的技巧，讀者可以更好地避免程式崩潰，提供友善的使用者體驗。
我們將探索函式的定義和調用，這是程式設計中非常重要且強大的概念，它可以將大型程式切割成小的、可重複使用的函式。讓我們一起來了解吧！函式的定義、呼叫和返回值是學習函式的核心。
我們探討了while迴圈的使用，不同於for迴圈，while迴圈以條件式判斷為基礎，而非限定重複次數。我們介紹了使用break語句強制結束迴圈，以及使用continue語句跳過特定程式碼並返回迴圈開頭，同時，我們提及了無窮迴圈的概念，強調了在迴圈中必須更改迴圈變數的值，以避免無窮迴圈的發生。
迴圈對象可以是列表或範圍，透過定義重複動作的內容，我們可以在迴圈中執行指定次數的操作。利用range函數，我們可以自訂重複執行的次數。同時，我們也介紹了break和continue的使用，以及巢狀迴圈的特性。