Combinatorial Counting¶
Table of Contents¶
- 62. Unique Paths (Medium)
- 357. Count Numbers with Unique Digits (Medium)
- 1175. Prime Arrangements (Easy)
- 3179. Find the N-th Value After K Seconds (Medium)
- 1359. Count All Valid Pickup and Delivery Options (Hard)
- 2400. Number of Ways to Reach a Position After Exactly k Steps (Medium)
- 2514. Count Anagrams (Hard)
- 3154. Find Number of Ways to Reach the K-th Stair (Hard)
- 1643. Kth Smallest Instructions (Hard)
- 2842. Count K-Subsequences of a String With Maximum Beauty (Hard)
- 1569. Number of Ways to Reorder Array to Get Same BST (Hard)
- 3405. Count the Number of Arrays with K Matching Adjacent Elements (Hard)
- 1866. Number of Ways to Rearrange Sticks With K Sticks Visible (Hard)
- 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls (Hard)
- 3272. Find the Count of Good Integers (Hard)
- 3317. Find the Number of Possible Ways for an Event (Hard)
- 1916. Count Ways to Build Rooms in an Ant Colony (Hard)
- 3343. Count Number of Balanced Permutations (Hard)
- 1830. Minimum Number of Operations to Make String Sorted (Hard)
- 2954. Count the Number of Infection Sequences (Hard)
- 3395. Subsequences with a Unique Middle Mode I (Hard)
- 1575. Count All Possible Routes (Hard)
- 3251. Find the Count of Monotonic Pairs II (Hard)
- 2539. Count the Number of Good Subsequences (Medium) 👑
- 634. Find the Derangement of An Array (Medium) 👑
- 1692. Count Ways to Distribute Candies (Hard) 👑
62. Unique Paths¶
"""
- Count the number of unique paths to reach the bottom-right corner of a `m x n` grid.
"""
# 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¶
-
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¶
-
Tags: Array, Math, Dynamic Programming, Backtracking, Combinatorics, Probability And Statistics