Dynamic Programming & Greedy Algorithms: Hướng Dẫn Toàn Diện

// TypeScript - Climbing Stairs
// Memoization (top-down)
function climbStairsMemo(n: number): number {
  const memo = new Map<number, number>();
 
  function dp(i: number): number {
    if (i <= 1) return 1;
    if (memo.has(i)) return memo.get(i)!;
 
    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }
 
  return dp(n);
}
 
// Tabulation (bottom-up)
function climbStairsTab(n: number): number {
  if (n <= 1) return 1;
  const dp = new Array(n + 1);
  dp[0] = 1;
  dp[1] = 1;
 
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
 
  return dp[n];
}
 
// Tối ưu space
function climbStairs(n: number): number {
  if (n <= 1) return 1;
  let prev2 = 1, prev1 = 1;
 
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
 
  return prev1;
}
 
console.log(climbStairs(5)); // 8

# Python - Climbing Stairs
from functools import lru_cache
 
# Memoization (top-down)
def climb_stairs_memo(n: int) -> int:
    @lru_cache(maxsize=None)
    def dp(i: int) -> int:
        if i <= 1:
            return 1
        return dp(i - 1) + dp(i - 2)
    return dp(n)
 
# Tabulation (bottom-up)
def climb_stairs_tab(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
 
# Tối ưu space
def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
 
print(climb_stairs(5))  # 8

// TypeScript - House Robber
function rob(nums: number[]): number {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
 
  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);
 
  for (let i = 2; i < nums.length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }
 
  return prev1;
}
 
console.log(rob([2, 7, 9, 3, 1])); // 12 (cướp nhà 0, 2, 4)

# Python - House Robber
def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
 
    prev2, prev1 = nums[0], max(nums[0], nums[1])
 
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
 
    return prev1
 
print(rob([2, 7, 9, 3, 1]))  # 12

// TypeScript - Coin Change
function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
 
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
 
  return dp[amount] === Infinity ? -1 : dp[amount];
}
 
console.log(coinChange([1, 5, 10, 25], 30)); // 2 (25 + 5)
console.log(coinChange([2], 3));              // -1

# Python - Coin Change
def coin_change(coins: list[int], amount: int) -> int:
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
 
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float("inf"):
                dp[i] = min(dp[i], dp[i - coin] + 1)
 
    return dp[amount] if dp[amount] != float("inf") else -1
 
print(coin_change([1, 5, 10, 25], 30))  # 2
print(coin_change([2], 3))               # -1

// TypeScript - Longest Increasing Subsequence
// Solution DP O(n²)
function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
 
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
 
  return Math.max(...dp);
}
 
// Tối ưu O(n log n) với binary search
function lengthOfLISOptimal(nums: number[]): number {
  const tails: number[] = []; // tail nhỏ nhất cho mỗi độ dài LIS
 
  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
 
  return tails.length;
}
 
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 → [2,3,7,101]

# Python - Longest Increasing Subsequence
# Solution DP O(n²)
def length_of_lis(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
 
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)
 
# Tối ưu O(n log n) với binary search
import bisect
 
def length_of_lis_optimal(nums: list[int]) -> int:
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)
 
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

// TypeScript - Unique Paths
function uniquePaths(m: number, n: number): number {
  const dp = new Array(n).fill(1);
 
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1]; // dp[j] đã có giá trị từ hàng trên
    }
  }
 
  return dp[n - 1];
}
 
console.log(uniquePaths(3, 7)); // 28

# Python - Unique Paths
def unique_paths(m: int, n: int) -> int:
    dp = [1] * n
 
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
 
    return dp[n - 1]
 
print(unique_paths(3, 7))  # 28

// TypeScript - Longest Common Subsequence
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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];
}
 
console.log(longestCommonSubsequence("abcde", "ace")); // 3 → "ace"

# Python - Longest Common Subsequence
def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
    return dp[m][n]
 
print(longest_common_subsequence("abcde", "ace"))  # 3

// TypeScript - Edit Distance
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1], // thay thế
          dp[i - 1][j],     // xóa
          dp[i][j - 1]      // chèn
        );
      }
    }
  }
 
  return dp[m][n];
}
 
console.log(minDistance("horse", "ros"));     // 3
console.log(minDistance("intention", "execution")); // 5

# Python - Edit Distance
def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # thay thế
                    dp[i - 1][j],      # xóa
                    dp[i][j - 1],      # chèn
                )
 
    return dp[m][n]
 
print(min_distance("horse", "ros"))      # 3
print(min_distance("intention", "execution"))  # 5

// TypeScript - 0/1 Knapsack
function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  // DP 1D tối ưu space
  const dp = new Array(capacity + 1).fill(0);
 
  for (let i = 0; i < n; i++) {
    // Duyệt ngược để tránh dùng vật phẩm i hai lần
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
 
  return dp[capacity];
}
 
console.log(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8)); // 10

# Python - 0/1 Knapsack
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [0] * (capacity + 1)
 
    for i in range(n):
        # Duyệt ngược để đảm bảo mỗi vật phẩm dùng tối đa một lần
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
 
    return dp[capacity]
 
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 10

// TypeScript - Partition Equal Subset Sum
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
 
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
 
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
 
  return dp[target];
}
 
console.log(canPartition([1, 5, 11, 5])); // true → [1,5,5] và [11]
console.log(canPartition([1, 2, 3, 5]));  // false

# Python - Partition Equal Subset Sum
def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
 
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
 
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
 
    return dp[target]
 
print(can_partition([1, 5, 11, 5]))  # True
print(can_partition([1, 2, 3, 5]))   # False

// TypeScript - Word Break
function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
 
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
 
  return dp[n];
}
 
console.log(wordBreak("leetcode", ["leet", "code"]));  // true
console.log(wordBreak("applepenapple", ["apple", "pen"])); // true

# Python - Word Break
def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
 
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
 
    return dp[n]
 
print(word_break("leetcode", ["leet", "code"]))   # True
print(word_break("applepenapple", ["apple", "pen"]))  # True

// TypeScript - Jump Game
function canJump(nums: number[]): boolean {
  let farthest = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
  }
 
  return true;
}
 
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false

# Python - Jump Game
def can_jump(nums: list[int]) -> bool:
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True
 
print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False

// TypeScript - Jump Game II
function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;
 
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
 
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }
 
  return jumps;
}
 
console.log(jump([2, 3, 1, 1, 4])); // 2

# Python - Jump Game II
def jump(nums: list[int]) -> int:
    jumps = 0
    current_end = 0
    farthest = 0
 
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
 
    return jumps
 
print(jump([2, 3, 1, 1, 4]))  # 2

// TypeScript - Non-overlapping Intervals (trả về số khoảng cần xóa tối thiểu)
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]); // Sắp xếp theo end time
 
  let count = 0;
  let prevEnd = -Infinity;
 
  for (const [start, end] of intervals) {
    if (start >= prevEnd) {
      prevEnd = end; // Giữ khoảng này
    } else {
      count++; // Xóa khoảng này (bị chồng)
    }
  }
 
  return count;
}
 
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1

# Python - Non-overlapping Intervals
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # Sắp xếp theo end time
    count = 0
    prev_end = float("-inf")
 
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end
        else:
            count += 1
 
    return count
 
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1

// TypeScript - Gas Station
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalTank = 0;
  let currentTank = 0;
  let start = 0;
 
  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    totalTank += net;
    currentTank += net;
 
    if (currentTank < 0) {
      start = i + 1;
      currentTank = 0;
    }
  }
 
  return totalTank >= 0 ? start : -1;
}
 
console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // 3

# Python - Gas Station
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total_tank = 0
    current_tank = 0
    start = 0
 
    for i in range(len(gas)):
        net = gas[i] - cost[i]
        total_tank += net
        current_tank += net
 
        if current_tank < 0:
            start = i + 1
            current_tank = 0
 
    return start if total_tank >= 0 else -1
 
print(can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]))  # 3