Dynamic programming
4 problems from Rosalind — Bioinformatics Textbook Track. Press Run on any block to execute it in your browser.
BA5A — Find the Minimum Number of Coins Needed to Make Change
solved Problem statement
The greedy answer is wrong here and that is the point: taking 25 first needs three coins where 20+20 needs two.
BA5C — Find a Longest Common Subsequence of Two Strings
solved Problem statement
lcs is a builtin. More than one subsequence is longest, so the assertion checks the length and that it really is a subsequence of both.
BA5B — Find the Length of a Longest Path in a Manhattan-like Grid
solved Problem statement
The grid is filled once in order and never revisited. Enumerating the paths would mean C(n+m, n) of them — 70 here, exponential in general. Longest path is NP-hard in general graphs; it is easy here only because the grid is acyclic.
BA5D — Find the Longest Path in a DAG
solved Problem statement
Easy for one reason: the graph is acyclic, so its nodes can be ordered with every edge pointing forwards and each score is final when read. Unreachable nodes stay at negative infinity rather than 0, or a detour through one could outscore a real path.