- Advanced Algorithms
- dynamic programming
- the reverse of recursion //反轉遞迴
- a recursive solution
- starts at the top and breaks the problem down solving all small problems until the complete problem is solved;
- a dynamic programming solution starts at the bottom, solving small problems and combining them to form an overall solution to the big problem.
- 例:
- Fibonacci Numbers
- Finding the Longest Common Substring
- The Knapsack Problem
- greedy algorithms :
- looks for “good solutions” as it works toward the complete solution. These good solutions, called local optima,
- will hopefully lead to the correct final solution, called the global optimum.
- greedy algorithms are used when it is almost impossible to find a complete solution, due to time and/or space considerations, yet a suboptimal solution is acceptable. //通常用於無法找到正確答案之時，因為其解可能因為時空的不同而有變化。
- 例:
- The Coin-Changing Problem
- Data Compression Using Huffman Coding
dynamic programming
通常解法優美，但是對於電腦的編譯器來說，是沒有效率的。
例: Finding the Longest Common Substring
例如 A=“raven” and B=“havoc”, the longest common substring is “av”.
用一個兩維array儲存比較的結果。初始是0，如果有match的位置就+1。
線上範例
Longest common subsequence
生物資訊系的人，常用來比較DNA序列。基因是由AGCT組成。
例如:
S1 DACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2 DGTCGTTCGGAATGCCGTTGCTCTGTAAA
要比較這兩序例有「多像」，這有許多解法。
1. explores algorithms: 其中一個string是另一個string的subet.
2. 其中一個string要變成另一個string時，所需要變化的字元最少。
如相機型號或是PS:字串相減?
3. 湊出第三個字串S3，其中S3是從S1與S2的特徵所組成。如S3 is GTCGTCGGAAGCCGGCCGAA.
