Jeremy Kun
Dynamic Programming Fail
2024-9-12
This is a story about a failure to apply dynamic programming to a woodworking project.
I’ve been building a shed in my backyard, and for one section I decided to build the floor by laying 2x4 planks side by side. I didn’t feel the need to join them with tongue-and-groove, but I did notice that using 2x4s alone wouldn’t fit the width they were supposed to fill.
I also had some 2x6 boards left over from a different part of the shed, and I realized that gave a neat dynamic programming problem: Can you fill a given width by laying planks of standard dimensional lumber?