Unique Paths
Easy About 10 min Free, no account needed
Count the robot's lattice paths across the grid.
The brief
A robot starts at the top-left of an m x n grid and moves only right or
down. Return the number of distinct paths to the bottom-right corner
(1 <= m, n <= 18, the answer fits a long).
The obvious approach recurses on both moves, 2^(m+n) calls. The hidden test is the
18 x 18 grid: about 2 billion paths, each walked separately by the recursion,
so it's too slow. You need to reach O(m * n) by reusing subresults instead of
recomputing them.
Starter code
using System;
public class Solution
{
// TODO: return the number of right/down lattice paths across an m x n grid.
public long UniquePaths(int m, int n)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Related katas
- Climbing Stairs Easy Free Count the ways up a staircase taking one or two steps at a time.
- Counting Bits Easy Free Popcounts for 0..n - reuse the table you are already building.
- House Robber Easy Free Maximize the loot without robbing two adjacent houses.
- Min Cost Climbing Stairs Easy Free Pay each step you land on; reach the top as cheaply as possible.