DSA sheet / Dynamic programming
Grid Paths I
Do these first: Dice Combinations
The problem in brief
You get an n by n grid (n up to 1000) where each cell is free or blocked. You start in the top-left corner and may only move right or down through free cells. Print the number of different paths to the bottom-right corner, modulo 10^9 + 7.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1638.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Think about the last move of a path: from which cells could it have arrived at a given cell?
-
If ways[r][c] counts the paths reaching cell (r, c), express it using the cells directly above and to the left.
-
What should ways be for a blocked cell? What about the start cell, especially if it is blocked?
-
Do you need the whole n by n table, or only the previous row?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
A counting problem on a grid where movement is monotone (only right or down) is a textbook DP. The brute force (enumerate every path with recursion) is exponential in n. But paths to different cells overlap heavily: every path to (r, c) ends by entering from (r - 1, c) or (r, c - 1), so ways(r, c) = ways(r - 1, c) + ways(r, c - 1). That recurrence only looks up and left, so fill the table row by row, left to right.
The blocked cells are just zeros: no path can be counted through them, so they contribute 0 to their neighbours. The start needs care: ways at the origin is 1 if it is free and 0 if it is blocked (a blocked start means no path at all). The habit: write the recurrence for a normal cell, then handle boundaries and obstacles as explicit special cases rather than hoping the general rule covers them.
Intuition
Water flowing over a grid: each free cell collects the water arriving from above and from the left and passes the total on to the right and downward. Blocked cells absorb nothing. The amount that ends up in the last cell is the answer.
Approach
- Read the grid rows.
- Keep a one-dimensional array
waysfor the current row. For each row r and column c: if the cell is blocked, set ways[c] = 0; else if r = 0 and c = 0, set it to 1; else ways[c] = (ways[c] from the row above + ways[c - 1] from the left) mod (10^9 + 7). - Print ways[n - 1] after the last row.
Pitfalls: if the top-left is blocked the answer is 0, which the rule above gives; the left neighbour only exists for c > 0; a 1 by 1 free grid has exactly one path. Memory is O(n) with the rolling row.
Complexity
O(n^2) time, O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
const int MOD = 1000000007;
vector<int> ways(n, 0);
for (int r = 0; r < n; r++) {
string row;
cin >> row;
for (int c = 0; c < n; c++) {
if (row[c] == '*') {
ways[c] = 0;
} else if (r == 0 && c == 0) {
ways[c] = 1;
} else {
if (c > 0) ways[c] += ways[c - 1]; // ways[c] still holds the cell above
if (ways[c] >= MOD) ways[c] -= MOD;
}
}
}
cout << ways[n - 1] << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
MOD = 10**9 + 7
ways = [0] * n
for r in range(n):
row = data[1 + r]
for c in range(n):
if row[c] == '*':
ways[c] = 0
elif r == 0 and c == 0:
ways[c] = 1
else:
left = ways[c - 1] if c > 0 else 0
ways[c] = (ways[c] + left) % MOD # ways[c] still holds the cell above
print(ways[n - 1])
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
final int MOD = 1_000_000_007;
int[] ways = new int[n];
for (int r = 0; r < n; r++) {
String row = in.readLine().trim();
for (int c = 0; c < n; c++) {
if (row.charAt(c) == '*') {
ways[c] = 0;
} else if (r == 0 && c == 0) {
ways[c] = 1;
} else {
if (c > 0) ways[c] += ways[c - 1]; // ways[c] still holds the cell above
if (ways[c] >= MOD) ways[c] -= MOD;
}
}
}
System.out.println(ways[n - 1]);
}
}const lines = require('fs').readFileSync(0, 'utf8').split('\n');
const n = Number(lines[0]);
const MOD = 1000000007;
const ways = new Int32Array(n);
for (let r = 0; r < n; r++) {
const row = lines[1 + r].trim();
for (let c = 0; c < n; c++) {
if (row[c] === '*') {
ways[c] = 0;
} else if (r === 0 && c === 0) {
ways[c] = 1;
} else {
if (c > 0) ways[c] += ways[c - 1]; // ways[c] still holds the cell above
if (ways[c] >= MOD) ways[c] -= MOD;
}
}
}
console.log(ways[n - 1]);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).