Chapter 3, Ways to Pass, Revisited

Hi everyone,

Just a quick post here to add an alternate solution for a problem in the book.

Remember that final example in Chapter 3 of Algorithmic Thinking, where we solved Ways to Pass? I provided a memoized solution there. (Be sure to take a look if the details are hazy.) I think it’s good practice to convert that to a dynamic programming solution. If you’d like to do so, you might do that before continuing to read here, because I’m going to present a dynamic programming solution next :D

Ways to Pass: Dynamic Programming Solution

Here’s my dynamic programming solution. I’ve also added this to the book’s code archive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//Not in the book, but here is a dynamic programming solution


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 70

int solve(int n, int t, int p) {
  int m, i, j;
  int dp[SIZE + 1][SIZE + 1];

  dp[0][0] = 1;
  for (i = 1; i <= t; i++)
    dp[0][i] = 0;

  for (i = 1; i <= n; i++)
    for (j = 0; j <= t; j++) {
      dp[i][j] = 0;
      for (m = p; m <= j; m++)
        dp[i][j] += dp[i - 1][j - m];
    }
  return dp[n][t];
}

int main(void) {
  int k, i, n, t, p;
  scanf("%d", &k);
  for (i = 0; i < k; i++) {
    scanf("%d%d%d", &n, &t, &p);
    printf("%d\n", solve(n, t, p));
  }
  return 0;
}

As with the memoized solution, we need a two-dimensional dynamic programming array here (12): the first dimension tracks the number of courses and the second tracks the number of marks to distribute. The base cases are the same as before (14-16).

Whoa, hold on: why are there so many nested loops here – three to be exact – when the memoized solution had only one loop? The reason is that we’re converting recursion to looping, and we need to fill in the entire two-dimensional dynamic programming table. So that’s two nested loops right there: one to range over the first dimension and the other, nested inside, to range over the second dimension. The third nested for-loop (21) is the same one that’s in the memoized solution: it tries all possible numbers of marks for the current course and adds up all of those smaller solutions.

There’s a general rule that’s worth remembering here: if you have a memoized solution with $q$ parameters that change on recursive calls, then a dynamic-programming solution is going to need $q$ nested loops (in addition to those loops that carry over from the memoized solution). In the memoized solution for Ways to Pass, there were two parameters that changed: n and t. (The other parameter in the memoized solution, p, never changes on recursive calls.) So our dynamic-programming solution has three nested loops: the one for n, the one for t, and the one that the memoized solution already had. To solidify this, you might revisit the Hockey Rivalry example in Chapter 3. There, the memoized solution had two parameters that change, and no loops, so the dynamic-programming solution has two nested loops.