Algorithms HomeWork#2 Due Date: 01.07.
(請用中文撰寫 A4 完整報告繳交)
 Dynamic programming (DP)是設計解決最佳解問題的演算法策略，請選
擇數個未在課程中教授過的DP之應用，收集並研讀相關資料以撰寫這
些利用DP應用所解決之問題的介紹、正確性及執行的效率。(助教會視
所挑選應用數量、深度與報告完整性來評分)
摘自維基百科:
[Dynamic programming] http://en.wikipedia.org/wiki/Dynamic_programming
Algorithms that use dynamic programming








Recurrent solutions to lattice models for protein-DNA binding
Backward induction as a solution method for finite-horizon discrete-time dynamic
optimization problems
Method of undetermined coefficients can be used to solve the Bellman equation in
infinite-horizon, discrete-time, discounted, time-invariant dynamic optimization
problems
Many string algorithms including longest common subsequence, longest
increasing subsequence, longest common substring, Levenshtein distance (edit
distance)
Many algorithmic problems on graphs can be solved efficiently for graphs of
bounded treewidth or bounded clique-width by using dynamic programming on a
tree decomposition of the graph.
The Cocke–Younger–Kasami (CYK) algorithm which determines whether and
how a given string can be generated by a given context-free grammar
Knuth's word wrapping algorithm that minimizes raggedness when word wrapping
text
…
[演算法筆記- Dynamic Programming (資料豐富)]
http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html

9. Thurgauer Karate-Nachwuchsmeisterschaft

Levenshtein Distanz - banane - 0 1 2 3 4 5 6 a 1 1 1 2 3 4 5 n

Julien Baste –

MAKERERE UNIVERSITY BUSINESS SCHOOL