Knapsack DP: capacity tables and grid paths · 1 of 2
Grid DP
Count the paths through a grid, find the cheapest path and the largest square of 1s, with one state per cell and a transition from the neighbouring cells.
Books1
Links2
- Paths on Grids Counting paths with blocked cells on CSES Grid Paths, then the longest common subsequence as a path through a grid. usaco.guide (opens in a new tab)
- Grid 1 The blocked-cell count of this lesson on a grid of up to 1,000 rows and 1,000 columns, with the answer modulo 10^9 + 7. atcoder.jp (opens in a new tab)