1. Nth Fibonacci Number
Problem: Given an integer n, calculate the nth Fibonacci number.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1
static Dictionary<int, long> memo = new Dictionary<int, long>();
static long Fibonacci(int n)
{
if (n <= 1)
return n;
if (memo.ContainsKey(n))
return memo[n];
memo[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
return memo[n];
}2. Counting Ways to Reach the Nth Stair
Problem: Given a staircase with n steps, you can climb either 1 or 2 steps at a time. How many distinct ways are there to reach the nth step?
static Dictionary<int, long> memo = new Dictionary<int, long>();
static long CountWaysToReachNthStair(int n)
{
if (n == 1) return 1;
if (n == 2) return 2;
if (memo.ContainsKey(n))
return memo[n];
memo[n] = CountWaysToReachNthStair(n - 1) + CountWaysToReachNthStair(n - 2);
return memo[n];
}3. Coin Change — Minimum Coins
Problem: Given an array coins of denominations and an integer amount, find the minimum number of coins needed to make up that amount. Return -1 if not possible.
coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)
coins = [2], amount = 3 → -1
static Dictionary<int, int> memo = new Dictionary<int, int>();
static int CoinChange(int[] coins, int amount)
{
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo.ContainsKey(amount))
return memo[amount];
int minCoins = int.MaxValue;
foreach (int coin in coins)
{
int newAmount = amount - coin;
if (newAmount >= 0)
{
int subproblem = CoinChange(coins, newAmount);
if (subproblem != -1)
minCoins = Math.Min(minCoins, subproblem + 1);
}
}
memo[amount] = (minCoins == int.MaxValue) ? -1 : minCoins;
return memo[amount];
}4. Maximum Subarray
Problem: Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 → subarray [4, -1, 2, 1]
public int MaxSubArray(int[] nums)
{
int n = nums.Length;
int[] memo = new int[n];
int maxSum = nums[0];
memo[0] = nums[0];
for (int i = 1; i < n; i++)
{
// Max subarray sum ending at i: either start fresh or extend the previous subarray
memo[i] = Math.Max(nums[i], nums[i] + memo[i - 1]);
maxSum = Math.Max(maxSum, memo[i]);
}
return maxSum;
}5. Coin Change II — Number of Combinations
Problem: Given an array coins and an integer amount, compute the number of combinations that make up that amount. You have an infinite supply of each coin.
coins = [1, 2, 5], amount = 5 → 4
Bottom-up DP
public int Change(int amount, int[] coins)
{
int[] dp = new int[amount + 1];
dp[0] = 1; // one way to make amount 0: use no coins
foreach (int coin in coins)
{
for (int i = coin; i <= amount; i++)
{
dp[i] += dp[i - coin];
}
}
return dp[amount];
}Memoization
public int Change(int amount, int[] coins)
{
Dictionary<string, int> memo = new Dictionary<string, int>();
return ChangeRecursive(amount, coins, 0, memo);
}
private int ChangeRecursive(int amount, int[] coins, int index, Dictionary<string, int> memo)
{
if (amount == 0) return 1; // valid combination found
if (amount < 0 || index == coins.Length) return 0;
string key = $"{amount}-{index}";
if (memo.ContainsKey(key))
return memo[key];
int include = ChangeRecursive(amount - coins[index], coins, index, memo);
int exclude = ChangeRecursive(amount, coins, index + 1, memo);
memo[key] = include + exclude;
return memo[key];
}6. Longest Common Subsequence (LCS)
Problem: Given two strings, find the length of their longest common subsequence. A subsequence preserves relative order but need not be contiguous.
str1 = "ABCD", str2 = "ACDF" → LCS = "ACD", length = 3
Bottom-up DP
public static int LongestCommonSubsequenceLength(string str1, string str2)
{
int m = str1.Length;
int n = str2.Length;
int[,] dp = new int[m + 1, n + 1];
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
dp[i, j] = 0;
else if (str1[i - 1] == str2[j - 1])
dp[i, j] = dp[i - 1, j - 1] + 1;
else
dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}
}
return dp[m, n];
}Memoization
public static int LongestCommonSubsequenceLength(string str1, string str2)
{
Dictionary<string, int> memo = new Dictionary<string, int>();
return LCSHelper(str1, str2, str1.Length, str2.Length, memo);
}
private static int LCSHelper(string str1, string str2, int m, int n, Dictionary<string, int> memo)
{
string key = m + "_" + n;
if (memo.ContainsKey(key))
return memo[key];
if (m == 0 || n == 0)
{
memo[key] = 0;
}
else if (str1[m - 1] == str2[n - 1])
{
memo[key] = 1 + LCSHelper(str1, str2, m - 1, n - 1, memo);
}
else
{
int opt1 = LCSHelper(str1, str2, m, n - 1, memo);
int opt2 = LCSHelper(str1, str2, m - 1, n, memo);
memo[key] = Math.Max(opt1, opt2);
}
return memo[key];
}7. Longest Increasing Subsequence (LIS)
Problem: Given an unsorted array of integers, find the length of the longest strictly increasing subsequence.
{ 10, 22, 9, 33, 21, 50, 41, 60, 80 } → LIS = {10, 22, 33, 50, 60, 80}, length = 6
Bottom-up DP
public static int LongestIncreasingSubsequenceLength(int[] nums)
{
if (nums == null || nums.Length == 0) return 0;
int n = nums.Length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = 1; // every element is an LIS of length 1
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
int maxLIS = 0;
for (int i = 0; i < n; i++)
{
if (dp[i] > maxLIS) maxLIS = dp[i];
}
return maxLIS;
}Memoization
public static int LongestIncreasingSubsequenceLength(int[] nums)
{
if (nums == null || nums.Length == 0) return 0;
int n = nums.Length;
int[] memo = new int[n];
for (int i = 0; i < n; i++) memo[i] = -1;
int maxLength = 1;
for (int i = 0; i < n; i++)
maxLength = Math.Max(maxLength, FindLISFromIndex(nums, i, memo));
return maxLength;
}
private static int FindLISFromIndex(int[] nums, int currentIndex, int[] memo)
{
if (memo[currentIndex] != -1)
return memo[currentIndex];
int maxLength = 1;
for (int i = 0; i < currentIndex; i++)
{
if (nums[currentIndex] > nums[i])
{
int subproblemLength = 1 + FindLISFromIndex(nums, i, memo);
maxLength = Math.Max(maxLength, subproblemLength);
}
}
memo[currentIndex] = maxLength;
return maxLength;
}