Dynamic programming is what allowed me to compute the number of legal Go positions [1,2], a 171 digit number.
While the naive method would take time 3^n^2 to examine all possible positions on an nxn board, dynamic programming effectively strips away one dimension, reducing time to O(n^5 * 5.4^n), while using space O(n * 5.4^n).
While the naive method would take time 3^n^2 to examine all possible positions on an nxn board, dynamic programming effectively strips away one dimension, reducing time to O(n^5 * 5.4^n), while using space O(n * 5.4^n).
[1] https://tromp.github.io/go/legal.html
[2] https://tromp.github.io/go/gostate.pdf