Activity: Dynamic Programming Practice
Learning Goals
You will work towards being able to…
- Design dynamic programming solutions to algorithmic problems
Activity
For each of the following questions, (1) design a recurrence relation, (2) provide pseudocode for a naive D&C solution, and finally (3) develop a dynamic programming algorithm to solve it. Consider the time and space complexity of your solutions. It WILL be helpful to play around with the problem specification to build intution (i.e., work through an example!) before jumping to designing an algorithm.
-
(Skiena 10-1) A child running up a staircase can hop between 1 and $k$ steps at a time. Suppose the staircase is $n$ steps tall. How many unique ways can the child climb the staircase? If you prefer a more math-y framing, how many unique sequences of integers $s_1, s_2, \dots, s_l$, where $\forall 1 \leq i \leq l, 1 \leq s_i \leq k$ exist such that $\sum s_i = n$?
-
(Skiena 10-5) Consider an $s$ x $t$ grid $G$ filled with non-negative numbers. Find a “path” from the top left to bottom right corner than minimizes the sum of numbers along the path. That is, you start at the top-left corner, and at each step can choose to move down within the same column or right within the same row.
Submission
Submit an artifact of your work on Moodle. You need not complete every (or even any) part, but you are responsible for eventually understanding how these problems work!