TypeScriptdp.ts
Copy
1
// Coin Change — minimum coins to make amount
2
function coinChange(coins: number[], amount: number): number {
3
  const dp = new Array(amount + 1).fill(Infinity);
4
  dp[0] = 0;
5
  for (let i = 1; i <= amount; i++) {
6
    for (const coin of coins) {
7
      if (coin <= i && dp[i - coin] + 1 < dp[i]) {
8
        dp[i] = dp[i - coin] + 1;
9
      }
10
    }
11
  }
12
  return dp[amount] === Infinity ? -1 : dp[amount];
13
}
14
 
15
// Longest Common Subsequence
16
function lcs(a: string, b: string): number {
17
  const m = a.length, n = b.length;
18
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
19
  for (let i = 1; i <= m; i++) {
20
    for (let j = 1; j <= n; j++) {
21
      dp[i][j] = a[i-1] === b[j-1] ? dp[i-1][j-1] + 1
22
                                     : Math.max(dp[i-1][j], dp[i][j-1]);
23
    }
24
  }
25
  return dp[m][n];
26
}
27
 
28
console.log(coinChange([1, 5, 10, 25], 36));  // 3 (25+10+1)
29
console.log(lcs('ABCBDAB', 'BDCAB'));          // 4 (BCAB)