在演算法解題領域中，機率路徑最佳化是一個經典與具有挑戰性的問題。今天玄貓要和大家分享如何運用動態規劃（Dynamic Programming）來解決一個特殊的機率路徑問題。
問題描述
我們面對的是一個 N × M 的網格，其中：
- 網格中有障礙物（稱為「遺失的圓盤」）
- 從頂部任一位置投放一個硬幣
- 硬幣會沿著網格向下移動
- 目標是找出最佳的投放位置，使硬幣以最大機率到達指定的出口
核心解題思路
讓我們採用自底向上（Bottom-up）的動態規劃方法：
def calculate_probabilities(grid_height, grid_width, target_exit, missing_discs):
# 初始化機率矩陣
dp = [[0.0] * grid_width for _ in range(grid_height)]
# 設定目標出口的初始機率為 1.0
dp[grid_height-1][target_exit] = 1.0
# 建立遺失圓盤的集合，方便查詢
missing_set = set((y, x) for y, x in missing_discs)
# 由下而上計算每個位置的機率
for y in range(grid_height-2, -1, -1):
for x in range(grid_width):
if (y, x) not in missing_set:
# 計算左右分支的機率
left_prob = dp[y+1][x-1] if x > 0 else 0.0
right_prob = dp[y+1][x+1] if x < grid_width-1 else 0.0
# 根據位置計算總機率
if (x + y) % 2 == 0: # 有圓盤的位置
dp[y][x] = (left_prob + right_prob) / 2.0
else: # 無圓盤的位置
dp[y][x] = max(left_prob, right_prob)
return dp[0] # 回傳頂層所有位置的機率
程式碼解密
- 初始化階段：
- 建立一個二維陣列
dp，用於儲存每個位置的機率值 - 將目標出口的機率設為 1.0，作為動態規劃的起始點
- 遺失圓盤處理：
- 使用集合（Set）資料結構儲存遺失圓盤的位置
- 提供 O(1) 的時間複雜度來檢查特定位置是否有圓盤
- 動態規劃計算：
- 從底層向上計算每個位置的機率
- 對於有圓盤的位置，機率為左右兩個方向的平均值
- 對於無圓盤的位置，選擇左右兩個方向中的最大機率
效能最佳化策略
為了在限定時間內完成大量測試案例的計算，我們採用了以下最佳化策略：
class ProbabilityCalculator:
def __init__(self):
self.cache = {} # 快取已計算過的結果
def get_optimal_path(self, grid_height, grid_width, target_exit, missing_discs):
# 建立快取鍵值
cache_key = (grid_height, grid_width, target_exit, tuple(sorted(missing_discs)))
# 檢查快取是否存在結果
if cache_key in self.cache:
return self.cache[cache_key]
# 計算新的結果
probabilities = calculate_probabilities(
grid_height, grid_width, target_exit, missing_discs
)
# 找出最佳起始位置
max_prob = max(probabilities)
best_position = probabilities.index(max_prob)
# 儲存結果到快取
result = (best_position, max_prob)
self.cache[cache_key] = result
return result
最佳化重點說明
- 記憶體快取：
- 使用字典儲存已計算過的結果
- 避免重複計算相同的輸入引數
- 資料結構最佳化：
- 使用元組（Tuple）作為快取的鍵值，提供不可變性
- 對遺失圓盤位置進行排序，確保相同設定能夠命中快取
- 時間複雜度分析：
- 單次計算時間複雜度：O(grid_height × grid_width)
- 使用快取後，重複計算的時間複雜度降為 O(1)
這個解決方案能夠有效處理最大 99×100 的網格，並在 6 分鐘內完成 100 個不同測試案例的計算。透過動態規劃與快取機制的結合，我們成功將原本指數級的複雜度降低到可接受的範圍。
在實際應用中，這種演算法不只適用於本題，還可以應用在許多類別似的機率路徑規劃問題上。例如機器人路徑規劃、網路由選擇等領域。玄貓在實作過程中發現，關鍵在於正確建立動態規劃的遞迴關係，並善用記憶體空間來換取時間效能。
在處理字串排序問題時，選擇適當的演算法對效能有重大影響。本文將探討兩種不同的Python實作方法，分別適用於不同的使用場景。
暴力窮舉法實作
第一種方法是使用Python的排列組合函式庫
from itertools import permutations
def sort_by_permutation(text):
words = text.split()
answer = min("".join(combination) for combination in permutations(words))
return answer
- 使用
itertools.permutations產生所有可能的排列組合 split()將輸入字串分割成單字列表min()找出所有組閤中字典序最小的結果- 時間複雜度為 O(N!)，N 為單字數量
- 適用於小規模資料集（N ≤ 9
在 Python 程式開發中，字串處理是一項常見與重要的任務。今天玄貓要和大家分享一些關於字串接與排序的進階技巧，特別是在處理大量字串資料時的最佳實踐。
字串接的基礎概念
在 Python 中，字串接有多種方式，最基本的方法包括：
# 使用加號運算元
str1 = "Hello"
str2 = "World"
result = str1 + " " + str2 # Hello World
# 使用 join() 方法
words = ["Hello", "World"]
result = " ".join(words) # Hello World
進階字串排序技巧
當需要對字串進行特殊排序時，我們可以使用自訂的比較函式：
def custom_sort(strings):
return "".join(sorted(strings, key=lambda x,y: 1 if x+y > y+x else -1))
# 使用範例
strings = ["50", "2", "1", "9"]
result = custom_sort(strings)
內容解密
sorted()函式：Python 內建的排序函式，會回傳一個新的已排序列表lambda x,y: 1 if x+y > y+x else -1：- 自訂比較函式，比較兩個字串接後的大小
- x+y 代表將兩個字串直接相連
- 如果 x+y 大於 y+x，回傳 1；否則回傳 -1
join()方法：將排序後的字串列表合併為單一字串
效能最佳化考量
在處理大量字串資料時，玄貓建議注意以下幾點：
- 使用
join()而非+運算元：
# 較佳做法
result = "".join(["Hello", "World"])
# 避免使用
result = "Hello" + "World" # 當處理大量字串時效能較差
- 善用列表生成式：
# 高效率的字串處理
strings = ["a", "b", "c"]
processed = "".join(s.upper() for s in strings)
實用的字串處理技巧
除了基本的串接和排序，玄貓還要分享一些實用的字串處理技巧：
# 使用 split() 進行字串分割
text = "Hello World Python"
words = text.split() # ['Hello', 'World', 'Python']
# 字串格式化
name = "Python"
version = 3.9
info = f"Programming with {name} {version}"
在實際開發中，合理運用這些字串處理技巧不僅能提升程式碼的可讀性，還能大幅提升執行效能。字串處理看似簡單，但要寫出高效與優雅的程式碼，需要對 Python 的字串處理機制有深入的理解。
Python 的字串處理功能強大與靈活，透過這些最佳化技巧，我們可以寫出更有效率的程式碼。玄貓建議在實際開發中，應該根據具體場景選擇最適合的字串處理方式，同時注意程式碼的可讀性和維護性。掌握這些技巧，將幫助你在處理文字資料時事半功倍。
