PrevNext
Not Frequent
 0/8

Paths on Grids

Authors: Nathan Chen, Michael Cao, Benjamin Qi, Andrew Wang

Counting the number of "special" paths on a grid, and how some string problems can be solved using grids.

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

Tutorial

A common archetype of DP Problems involves a 2D grid of square cells (like graph paper), and we have to analyze "paths." A path is a sequence of cells whose movement is restricted to one direction on the xx-axis and one direction on the yy-axis (for example, you may only be able to move down or to the right). Usually, the path also has to start in one corner of the grid and end on another corner. The problem may ask you to count the number of paths that satisfy some property, or it may ask you to find the max/min of some quantity over all paths.

Usually, the sub-problems in this type of DP are a sub-rectangle of the whole grid. For example, consider a problem in which we count the number of paths from (1,1)(1, 1) to (N,M)(N, M) when we can only move in the positive xx-direction and the positive yy-direction.

Let dp(x,y)dp(x, y) be the number of paths in the sub-rectangle whose corners are (1,1)(1, 1) and (x,y)(x, y). We know that the first cell in a path counted by dp(x,y)dp(x, y) is (1,1)(1, 1), and we know the last cell is (x,y)(x, y). However, the second-to-last cell can either be (x1,y)(x-1, y) or (x,y1)(x, y-1). Thus, if we pretend to append the cell (x,y)(x, y) to the paths that end on (x1,y)(x-1, y) or (x,y1)(x, y-1), we construct paths that end on (x,y)(x, y). Working backwards like that motivates the following recurrence: dp(x,y)=dp(x1,y)+dp(x,y1)dp(x, y) = dp(x-1, y) + dp(x, y-1). We can use this recurrence to calculate dp(N,M)dp(N, M). Keep in mind that dp(1,1)=1dp(1, 1) = 1 because the path to (1,1)(1, 1) is just a single cell. In general, thinking about how you can append cells to paths will help you construct the correct DP recurrence.

When using the DP recurrence, it's important that you compute the DP values in an order such that the dp-value for a cell is known before you use it to compute the dp-value for another cell. In the example problem above, it's fine to iterate through each row from 00 to M1M-1:

C++

1for(int i = 0; i < M; i++) {
2 for(int j = 0; j < N; j++) {
3 if(j > 0) dp[j][i] += dp[j-1][i];
4 if(i > 0) dp[j][i] += dp[j][i-1];
5 }
6}

Java

1for(int i = 0; i < M; i++) {
2 for(int j = 0; j < N; j++) {
3 if(j > 0) dp[j][i] += dp[j-1][i];
4 if(i > 0) dp[j][i] += dp[j][i-1];
5 }
6}

Note how the coordinates in the code are in the form (x coordinate, y coordinate). Most of the time, it's more convenient to think of points as (row, column) instead, which swaps the order of the coordinates, though the code uses the former format to be consistent with the definition of dp(x,y)dp(x, y).

Solution - Grid Paths

In this problem, we are directly given a 2D grid of cells, and we have to count the number of paths from corner to corner that can only go down (positive yy direction) and to the right (positive xx direction), with a special catch. The path can't use a cell marked with an asterisk.

We come close to being able to use our original recurrence, but we have to modify it. Basically, if a cell (x,y)(x, y) is normal, we can use the recurrence normally. But, if cell (x,y)(x, y) has an asterisk, the dp-value is 00, because no path can end on a trap.

dp(x,y)={dp(x1,y)+dp(x,y1)if (x,y) is not a trap0,if (x,y) is a trap dp(x, y) = \begin{cases} dp(x-1, y) + dp(x, y-1) & \text{if $(x, y)$ is not a trap} \\ 0, & \text{if $(x, y)$ is a trap} \end{cases}

The code for the DP recurrence doesn't change much:

C++

1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6
7bool ok[1000][1000];
8ll dp[1000][1000];
9
10int main() {

Java

1import java.util.*;
2import java.io.*;
3
4public class Main {
5
6 public static void main(String[] args) throws Exception {
7 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
8
9 int N = Integer.parseInt(br.readLine());
10 long dp[][] = new long[N][N];

Note how the coordinates are now in the form (row, column) when reading in the input.

Solution - Longest Common Subsequence

The longest common subsequence is a classical string problem, but where's the grid?

In fact, we can create a grid to solve it. Think about the following algorithm to create any (not necessarily the longest) subsequence between two strings AA and BB:

  • We start with two pointers, ii, and jj, each beginning at 00.
  • We do some "action" at each time step, until there are no more available "actions". An "action" can be any of the following:
  1. Increase the value of ii by 11 (only works if i<Ai < |A|).
  2. Increase the value of jj by 11 (only works if j<Bj < |B|).
  3. Increase the value of ii and jj by 11 only if Ai=BjA_i = B_j. Append that character AiA_i (or BjB_j) to the common subsequence. (only works if i<Ai < |A| and j<Bj < |B|).
  • We know that this process creates a common subsequence because characters which are common to both strings are found from left to right.

This algorithm can also be illustrated on a grid. Let A:=xabcdA := xabcd and B:=yazcB := yazc. Then, the current state of the algorithm can be defined as a specific point (i,j)(i, j) using the values of ii and jj that we discussed previously. The process of increasing pointers can be seen as moving right (if ii is increased), moving down (if jj is increased), or moving diagonally (if both ii and jj increase). See that each diagonal movement adds one to the length of the common subsequence.

Now, we re-phrase "the length of the longest increasing subsequence" as "the maximum number of 'diagonal movements' ("action 3" in the above algorithm) in a path from the top-left corner to the bottom-right corner on the grid." Thus, we have constructed a grid-type DP problem.

xabcd
y00000
a01111
z01111
c01122

In the above grid, see how the bolded path has diagonal movements at characters "a" and "c". That means the longest common subsequence between "xabcd" and "yazc" is "ac".

Based on the three "actions", which are also the three possible movements of the path, we can create a DP-recurrence to find the longest common subsequence:

dp(i,j)={max(dp(i1,j),dp(i,j1))if AiBjdp(i1,j1)+1,if Ai=Bjdp(i, j) = \begin{cases} \max(dp(i-1, j), dp(i, j-1)) & \text{if }A_i \neq B_j \\ dp(i-1,j-1)+1, & \text{if }A_i = B_j \end{cases}

C++

1class Solution {
2public:
3 int longestCommonSubsequence(string a, string b) {
4 int dp[a.size()][b.size()];
5 for (int i = 0; i < a.size(); i++) {
6 fill(dp[i], dp[i]+b.size(), 0);
7 }
8 for (int i = 0; i < a.size(); i++) {
9 if(a[i] == b[0]) dp[i][0] = 1;
10 if(i != 0) dp[i][0] = max(dp[i][0], dp[i-1][0]);

Ben - shorter version using macros:

1class Solution {
2public:
3 int longestCommonSubsequence(str a, str b) {
4 V<vi> dp(sz(a)+1,vi(sz(b)+1));
5 F0R(i,sz(a)+1) F0R(j,sz(b)+1) {
6 if (i < sz(a)) ckmax(dp[i+1][j],dp[i][j]);
7 if (j < sz(b)) ckmax(dp[i][j+1],dp[i][j]);
8 if (i < sz(a) && j < sz(b))
9 ckmax(dp[i+1][j+1],dp[i][j]+(a[i] == b[j]));
10 }

Java

1class Solution {
2 public int longestCommonSubsequence(String a, String b) {
3 int[][] dp = new int[a.length()][b.length()];
4 for (int i = 0; i < a.length(); i++) {
5 if(a.charAt(i) == b.charAt(0)) dp[i][0] = 1;
6 if(i != 0) dp[i][0] = Math.max(dp[i][0], dp[i-1][0]);
7 }
8 for (int i = 0; i < b.length(); i++) {
9 if(a.charAt(0) == b.charAt(i)) {
10 dp[0][i] = 1;

Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

DP

CSESEasy
Show Tags

DP

GoldEasy
Show Tags

DP

External Sol
GoldEasy
Show Tags

DP

External Sol
GoldNormal
Show Tags

DP

External Sol
Old GoldHard
Show Tags

DP

External Sol
Optional

Don't expect you to solve this task at this level, but you might find it interesting:

Circular Longest Common Subsequence

Module Progress:

Give Us Feedback on Paths on Grids!

PrevNext