Dynamic programming: grids and sequences
Apply DP to two-dimensional grids (counting paths around obstacles, cheapest route) and to sequences (longest increasing subsequence, maximum subarray with Kadane’s algorithm).
Counting paths on a grid
paths[r, c] = paths[r − 1, c] + paths[r, c − 1], and a blocked cell has 0.
string[] site ={ "......", "..#...", "...#..", "......", "..#..."};Console.WriteLine(CountPaths(site)); static long CountPaths(string[] g){ int rows = g.Length, cols = g[0].Length; var paths = new long[rows, cols]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (g[r][c] == '#') continue; // blocked: stays 0 if (r == 0 && c == 0) { paths[r, c] = 1; continue; } long fromAbove = r > 0 ? paths[r - 1, c] : 0; long fromLeft = c > 0 ? paths[r, c - 1] : 0; paths[r, c] = fromAbove + fromLeft; } return paths[rows - 1, cols - 1];}30
The cheapest route
best[r, c] = cost[r, c] + min(best above, best left). To recover the route itself, walk back from the corner, always to the cheaper neighbour.
int[,] cost ={ { 1, 3, 1, 2, 8, 1 }, { 1, 5, 1, 9, 1, 2 }, { 4, 2, 1, 3, 2, 6 }, { 7, 1, 8, 1, 1, 2 }, { 2, 4, 1, 5, 3, 1 }};Console.WriteLine(MinPathSum(cost)); static int MinPathSum(int[,] cost){ int rows = cost.GetLength(0), cols = cost.GetLength(1); var best = new int[cols]; // one row is enough for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (r == 0 && c == 0) best[c] = cost[0, 0]; else if (r == 0) best[c] = best[c - 1] + cost[r, c]; // only from the left else if (c == 0) best[c] = best[c] + cost[r, c]; // only from above else best[c] = Math.Min(best[c], best[c - 1]) + cost[r, c]; // above vs left } return best[cols - 1];}15
best[c] still holds the value from the row above until it is overwritten, so one array of length cols replaces the whole table. Time O(rows × cols), memory O(cols).
Longest increasing subsequence
{ 3, 10, 2, 1, 20, 4, 6, 7 }. What is the longest run of readings that keeps increasing, if you may skip some (a subsequence, not necessarily consecutive)? State: lis[i] = length of the longest increasing subsequence that ends at i. Recurrence: look at every earlier j with a smaller value and extend the best one.
int[] readings = { 3, 10, 2, 1, 20, 4, 6, 7 };Console.WriteLine(Lis(readings));Console.WriteLine(LisFast(readings)); static int Lis(int[] a) // O(n²){ var lis = new int[a.Length]; for (int i = 0; i < a.Length; i++) { lis[i] = 1; // just a[i] on its own for (int j = 0; j < i; j++) if (a[j] < a[i]) lis[i] = Math.Max(lis[i], lis[j] + 1); } return a.Length == 0 ? 0 : lis.Max();} static int LisFast(int[] a) // O(n log n){ var tails = new List<int>(); // tails[k] = smallest end of an increasing run of length k + 1 foreach (int x in a) { int pos = tails.BinarySearch(x); if (pos < 0) pos = ~pos; // where x would be inserted if (pos == tails.Count) tails.Add(x); // extends the longest run else tails[pos] = x; // a smaller end for that length } return tails.Count;}4 4
~index trick from the searching lesson) to update it. It is a good example of DP and binary search working together.
Sequence DP: the pattern
| Problem | State | Recurrence |
|---|---|---|
{ -2, 1, -3, 4, -1, 2, 1, -5, 4 } → 6 (4 − 1 + 2 + 1); the profit data from the divide-and-conquer lesson { 3, -8, 5, -1, 6, -9, 4, 2, -3 } → 10.
Show a hint
endingHere = max(x, endingHere + x). Track the largest value it ever takes.
Show the solution
Console.WriteLine(Kadane(new[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }));Console.WriteLine(Kadane(new[] { 3, -8, 5, -1, 6, -9, 4, 2, -3 })); static int Kadane(int[] a){ int endingHere = a[0], best = a[0]; for (int i = 1; i < a.Length; i++) { endingHere = Math.Max(a[i], endingHere + a[i]); // start fresh or extend best = Math.Max(best, endingHere); } return best;}6 10
Remember
Grid DP: a cell’s answer comes from the neighbours its last move came from. Counting uses “+”, optimising uses “min” or “max”; walk back from the end to recover the route. Rolling arrays cut memory from O(rows × cols) to O(cols). Sequence DP: define the state as “the best ending at i”; LIS and Kadane are the classic examples.