796 Fundamental

796-counting-paths-dp — Counting Paths

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "796-counting-paths-dp — Counting Paths" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Counting the number of distinct paths in a grid from top-left to bottom-right (moving right or down) is a combinatorics problem solvable by DP. Key difference from OCaml: 1. **Pascal connection**: `dp[i][j] = dp[i

Tutorial

The Problem

Counting the number of distinct paths in a grid from top-left to bottom-right (moving right or down) is a combinatorics problem solvable by DP. The answer without obstacles is C(m+n-2, m-1) — a binomial coefficient — but obstacles require DP. This problem models robot motion planning, network routing analysis, and combinatorial counting. The obstacle variant uses the same recurrence with zeroed cells.

🎯 Learning Outcomes

• Implement unique_paths(m, n) filling dp[i][j] = dp[i-1][j] + dp[i][j-1]

• Handle the obstacle variant unique_paths_obstacles by zeroing blocked cells

• Understand that the answer without obstacles equals the binomial coefficient C(m+n-2, m-1)

• Optimize space from O(mn) to O(n) using a single rolling row

• See how this relates to Pascal's triangle

Code Example

#![allow(clippy::all)]
//! # Counting Paths

pub fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1; n]; m];
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    dp[m - 1][n - 1]
}

pub fn unique_paths_obstacles(grid: &[Vec<i32>]) -> usize {
    if grid.is_empty() || grid[0][0] == 1 {
        return 0;
    }
    let (m, n) = (grid.len(), grid[0].len());
    let mut dp = vec![vec![0usize; n]; m];
    dp[0][0] = 1;
    for j in 1..n {
        dp[0][j] = if grid[0][j] == 1 { 0 } else { dp[0][j - 1] };
    }
    for i in 1..m {
        dp[i][0] = if grid[i][0] == 1 { 0 } else { dp[i - 1][0] };
    }
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = if grid[i][j] == 1 {
                0
            } else {
                dp[i - 1][j] + dp[i][j - 1]
            };
        }
    }
    dp[m - 1][n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_paths() {
        assert_eq!(unique_paths(3, 7), 28);
    }
}

(* Counting Paths in Grid with Obstacles — DP O(m×n) *)
(* grid.(i).(j) = 0 means open, 1 means obstacle *)

let count_paths grid =
  let m = Array.length grid in
  if m = 0 then 0
  else begin
    let n  = Array.length grid.(0) in
    let dp = Array.make_matrix m n 0 in
    (* Start must be open *)
    if grid.(0).(0) = 1 then 0
    else begin
      dp.(0).(0) <- 1;
      (* First row *)
      for j = 1 to n - 1 do
        dp.(0).(j) <- if grid.(0).(j) = 0 then dp.(0).(j-1) else 0
      done;
      (* First col *)
      for i = 1 to m - 1 do
        dp.(i).(0) <- if grid.(i).(0) = 0 then dp.(i-1).(0) else 0
      done;
      (* Rest *)
      for i = 1 to m - 1 do
        for j = 1 to n - 1 do
          dp.(i).(j) <- if grid.(i).(j) = 1 then 0
                        else dp.(i-1).(j) + dp.(i).(j-1)
        done
      done;
      dp.(m-1).(n-1)
    end
  end

let () =
  let grid1 = [| [|0;0;0|]; [|0;1;0|]; [|0;0;0|] |] in
  Printf.printf "3×3 grid with center obstacle: %d paths\n" (count_paths grid1);

  let grid2 = [| [|0;0;0|]; [|0;0;0|]; [|0;0;0|] |] in
  Printf.printf "3×3 open grid: %d paths\n" (count_paths grid2);

  let grid3 = [| [|0;1|]; [|0;0|] |] in
  Printf.printf "2×2 grid [[0,1],[0,0]]: %d paths\n" (count_paths grid3)

Key Differences

Pascal connection: dp[i][j] = dp[i-1][j] + dp[i][j-1] is Pascal's recurrence rotated 45 degrees; both languages show this connection naturally.

Obstacle handling: Both languages require careful boundary initialization — an obstacle in row 0 or column 0 blocks all subsequent boundary cells.

Overflow: For large grids (100×100), path counts exceed u64 range; both languages need big integer support (BigInt/Zarith).

Space optimization: A single-row DP reduces space to O(n); dp[j] += dp[j-1] in a left-to-right pass works correctly.

OCaml Approach

OCaml implements with Array.make_matrix m n 0 and explicit boundary initialization. The obstacle check grid.(i).(j) = 1 blocks paths. Functional style can express this as let dp = Array.init m (fun i -> Array.init n (fun j -> if i=0 || j=0 then 1 else dp.(i-1).(j) + dp.(i).(j-1))) but requires mutual reference tricks. Pascal's triangle connection: dp[i][j] equals C(i+j, i) in the obstacle-free case.

Full Source

#![allow(clippy::all)]
//! # Counting Paths

pub fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1; n]; m];
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    dp[m - 1][n - 1]
}

pub fn unique_paths_obstacles(grid: &[Vec<i32>]) -> usize {
    if grid.is_empty() || grid[0][0] == 1 {
        return 0;
    }
    let (m, n) = (grid.len(), grid[0].len());
    let mut dp = vec![vec![0usize; n]; m];
    dp[0][0] = 1;
    for j in 1..n {
        dp[0][j] = if grid[0][j] == 1 { 0 } else { dp[0][j - 1] };
    }
    for i in 1..m {
        dp[i][0] = if grid[i][0] == 1 { 0 } else { dp[i - 1][0] };
    }
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = if grid[i][j] == 1 {
                0
            } else {
                dp[i - 1][j] + dp[i][j - 1]
            };
        }
    }
    dp[m - 1][n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_paths() {
        assert_eq!(unique_paths(3, 7), 28);
    }
}

(* Counting Paths in Grid with Obstacles — DP O(m×n) *)
(* grid.(i).(j) = 0 means open, 1 means obstacle *)

let count_paths grid =
  let m = Array.length grid in
  if m = 0 then 0
  else begin
    let n  = Array.length grid.(0) in
    let dp = Array.make_matrix m n 0 in
    (* Start must be open *)
    if grid.(0).(0) = 1 then 0
    else begin
      dp.(0).(0) <- 1;
      (* First row *)
      for j = 1 to n - 1 do
        dp.(0).(j) <- if grid.(0).(j) = 0 then dp.(0).(j-1) else 0
      done;
      (* First col *)
      for i = 1 to m - 1 do
        dp.(i).(0) <- if grid.(i).(0) = 0 then dp.(i-1).(0) else 0
      done;
      (* Rest *)
      for i = 1 to m - 1 do
        for j = 1 to n - 1 do
          dp.(i).(j) <- if grid.(i).(j) = 1 then 0
                        else dp.(i-1).(j) + dp.(i).(j-1)
        done
      done;
      dp.(m-1).(n-1)
    end
  end

let () =
  let grid1 = [| [|0;0;0|]; [|0;1;0|]; [|0;0;0|] |] in
  Printf.printf "3×3 grid with center obstacle: %d paths\n" (count_paths grid1);

  let grid2 = [| [|0;0;0|]; [|0;0;0|]; [|0;0;0|] |] in
  Printf.printf "3×3 open grid: %d paths\n" (count_paths grid2);

  let grid3 = [| [|0;1|]; [|0;0|] |] in
  Printf.printf "2×2 grid [[0,1],[0,0]]: %d paths\n" (count_paths grid3)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_paths() {
        assert_eq!(unique_paths(3, 7), 28);
    }
}

Deep Comparison

OCaml vs Rust: Counting Paths Dp

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement the space-optimized O(n) version using a single row, verifying it produces the same results as the 2D version.

Add support for a start and end position anywhere in the grid (not restricted to corners), modifying the initialization and boundary conditions.

Solve the 3D variant: counting paths in an m×n×p cube from (0,0,0) to (m-1,n-1,p-1) moving only right, down, or forward.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust