PrevNext
Not Frequent
 0/11

Paths on Grids

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

Contributor: Maggie Liu

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

Edit This Page

Focus Problem – try your best to solve this problem before continuing!

Focus Problem – try your best to solve 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]\texttt{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]\texttt{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]\texttt{dp}[x][y] = \texttt{dp}[x-1][y] + \texttt{dp}[x][y-1]. We can use this recurrence to calculate dp[N][M]\texttt{dp}[N][M]. Keep in mind that dp[1][1]=1\texttt{dp}[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++

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

Java

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

Python

for i in range(M):
for j in range(N):
if j > 0:
dp[j][i] += dp[j - 1][i]
if i > 0:
dp[j][i] += dp[j][i - 1]

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]\texttt{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\texttt{dp}[x][y] = \begin{cases} \texttt{dp}[x-1][y] + \texttt{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++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ok[1000][1000];
ll dp[1000][1000];
int main() {

Java

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long dp[][] = new long[N][N];

Python

n = int(input())
ok = [[char == "." for char in input()] for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(n):
# if current square is a trap
if not ok[i][j]:
dp[i][j] = 0

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=Bj\texttt{dp}[i][j] = \begin{cases} \max(\texttt{dp}[i-1][j], \texttt{dp}[i][j-1]) & \text{if }A_i \neq B_j \\ \texttt{dp}[i-1][j-1]+1, & \text{if }A_i = B_j \end{cases}

C++

class Solution {
public:
int longestCommonSubsequence(string a, string b) {
int dp[a.size()][b.size()];
for (int i = 0; i < a.size(); i++) { fill(dp[i], dp[i] + b.size(), 0); }
for (int i = 0; i < a.size(); i++) {
if (a[i] == b[0]) dp[i][0] = 1;
if (i != 0) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
}
for (int i = 0; i < b.size(); i++) {

Ben - shorter version using macros:

Code Snippet: Benq Template (Click to expand)
class Solution {
public:
int longestCommonSubsequence(str a, str b) {
V<vi> dp(sz(a) + 1, vi(sz(b) + 1));
F0R(i, sz(a) + 1) F0R(j, sz(b) + 1) {
if (i < sz(a)) ckmax(dp[i + 1][j], dp[i][j]);
if (j < sz(b)) ckmax(dp[i][j + 1], dp[i][j]);
if (i < sz(a) && j < sz(b))
ckmax(dp[i + 1][j + 1], dp[i][j] + (a[i] == b[j]));
}
return dp[sz(a)][sz(b)];
}
};

Java

class Solution {
public int longestCommonSubsequence(String a, String b) {
int[][] dp = new int[a.length()][b.length()];
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) == b.charAt(0)) dp[i][0] = 1;
if (i != 0) dp[i][0] = Math.max(dp[i][0], dp[i - 1][0]);
}
for (int i = 0; i < b.length(); i++) {
if (a.charAt(0) == b.charAt(i)) { dp[0][i] = 1; }
if (i != 0) dp[0][i] = Math.max(dp[0][i], dp[0][i - 1]);

Python

class Solution:
def longestCommonSubsequence(self, a: str, b: str) -> int:
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[len(a)][len(b)]

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDP
CSESEasy
Show TagsDP
GoldEasy
Show TagsDP
GoldEasy
Show TagsDP
GoldNormal
Show TagsDP
ACNormal
Show TagsDP
Old GoldHard
Show TagsDP
GoldHard
Show TagsDP
GoldVery Hard
Show TagsDP, Greedy

Optional

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

Circular Longest Common Subsequence

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext