jonnifyelixir
F4 / F4.11 / tabulation

F4.11 · part 2 of 3 · the credit target

Tabulation & bottom-up

A certificate needs a fixed number of credits, and modules are worth one, three, or four credits each. What is the fewest modules that sum to the target exactly? The answer for a total is one more than the best answer for that total minus a module’s worth — optimal substructure. Tabulation builds it bottom-up: fill a table of the fewest modules for every total from zero upward, and the target’s answer is the last cell, read off the smaller ones already computed.

Pick a target and watch the table fill from zero. The grabby choice — take the biggest module that fits — is not always optimal; the table always is.

Fill from zero up Advanced: why greedy can lose

Fill from zero up

Cell dp[c] is the fewest modules summing to c. It is 1 + min(dp[c-1], dp[c-3], dp[c-4]) over the module worths that fit, with dp[0] = 0. Each cell uses only smaller cells, so a left-to-right pass fills the whole table. Pick the target.

Target credits · select one · modules worth 1, 3, 4

dp[c] = fewest modules summing to c credits dp[6] = 1 + dp[3] = 2 two modules (3 + 3) — greedy would use three 

      

      
target: 6 credits

      
fewest modules: 2 modules

    

    
Every cell is solved once, smallest first, and the target reads straight off the table. Because
      each cell weighs all module choices, the table never gets trapped by a greedy first move.

  


  

    
Advanced: why greedy can lose

    

      
Greedy takes the largest module that fits and repeats. For a target of six that is four, then two ones
        — three modules — because the leading four strands a remainder of two that only ones can fill. The
        table does better: two threes, two modules. The difference is that greedy commits to a locally largest step,
        while dp[c] compares every module worth and keeps the best, so a worse-looking
        step now that sets up a better finish is never ruled out.

      
Tabulation suits this because the table is dense — the answer for the target genuinely needs the answers
        for the smaller totals beneath it, so computing them all wastes nothing, and the bottom-up loop avoids a deep
        recursion. It is the same solve-each-once as memoisation, run eagerly from the base case up rather than lazily
        from the target down; here that trades the cache lookups for a flat pass over a list of totals.

    

    
# fewest modules (worth 1, 3, 4) to reach `target` credits
def fewest(target, worths \\ [1, 3, 4]) do
  Enum.reduce(1..target//1, %{0 => 0}, fn c, dp ->
    best =
      worths
      |> Enum.filter(&(&1 <= c))
      |> Enum.map(&(dp[c - &1] + 1))    # 1 + a smaller, already-filled cell
      |> Enum.min(fn -> :infinity end)
    Map.put(dp, c, best)
  end)[target]
end

    

      

        
greedy

        
Largest module first — can strand a remainder and lose.

      

      
      

        
a bottom-up table

        
Every total solved from zero up, weighing all worths; the target is optimal.

      

    

    
Next: a classic problem
      — edit distance as a two-dimensional table, powering typo-tolerant search.

  


  

    
References

    
Primary sources for this lesson, and where it connects in the course.

    

      
Sources

      
      
Related in this course