Skip to content

Combinatorial Counting

Table of Contents

62. Unique Paths

"""
-   Count the number of unique paths to reach the bottom-right corner of a `m x n` grid.

![62](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)
"""


# DP - 2D
def uniquePaths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1

    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[-1][-1]


print(uniquePaths(m=3, n=7))  # 28
# [[1, 1, 1,  1,  1,  1,  1],
#  [1, 2, 3,  4,  5,  6,  7],
#  [1, 3, 6, 10, 15, 21, 28]]

#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector dp(m, vector<int>(n, 1));

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

int main() {
    int m = 3, n = 7;
    cout << uniquePaths(m, n) << endl;  // 28
    return 0;
}

357. Count Numbers with Unique Digits

1175. Prime Arrangements

3179. Find the N-th Value After K Seconds

1359. Count All Valid Pickup and Delivery Options

2400. Number of Ways to Reach a Position After Exactly k Steps

2514. Count Anagrams

3154. Find Number of Ways to Reach the K-th Stair

1643. Kth Smallest Instructions

2842. Count K-Subsequences of a String With Maximum Beauty

1569. Number of Ways to Reorder Array to Get Same BST

  • LeetCode | 力扣

  • Tags: Array, Math, Divide And Conquer, Dynamic Programming, Tree, Union Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree

3405. Count the Number of Arrays with K Matching Adjacent Elements

1866. Number of Ways to Rearrange Sticks With K Sticks Visible

1467. Probability of a Two Boxes Having The Same Number of Distinct Balls

  • LeetCode | 力扣

  • Tags: Array, Math, Dynamic Programming, Backtracking, Combinatorics, Probability And Statistics

3272. Find the Count of Good Integers

3317. Find the Number of Possible Ways for an Event

1916. Count Ways to Build Rooms in an Ant Colony

3343. Count Number of Balanced Permutations

1830. Minimum Number of Operations to Make String Sorted

2954. Count the Number of Infection Sequences

3395. Subsequences with a Unique Middle Mode I

1575. Count All Possible Routes

3251. Find the Count of Monotonic Pairs II

2539. Count the Number of Good Subsequences

634. Find the Derangement of An Array

1692. Count Ways to Distribute Candies

Comments