Vectorized Checkerboard
08/04/2024
In this series I am implementing Dynamic Programming Katas with vectorized implementations.
The first post explored the Vectorized Longest Increasing Subsequence problem, and in this post I will dive into the Checkerboard problem.
Introduction
Consider a checkerboard with n*n squares and a cost function c(i, j) which returns a cost associated with the indexes of (i,j). The checker starts in the first row. We would like to know the shortest path (the sum of the minimum costs at each visited row) to get to the last row. The checker could move only diagonally left forward, diagonally right forward, or straight forward. That is, a checker on (1,3) can move to (2,2), (2,3) or (2,4).