Coin Change Problem
Mô tả nguyên lý
Tìm số lượng đồng tiền tối thiểu để tạo ra một tổng tiền cho trước.
Cài đặt mẫu (Implementation)
function coinChanges($coins, $amount) {
$dp = array_fill(0, $amount + 1, $amount + 1);
$dp[0] = 0;
for ($i = 1; $i <= $amount; $i++) {
foreach ($coins as $coin) {
if ($i - $coin >= 0) $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
}
}
return $dp[$amount] > $amount ? -1 : $dp[$amount];
}
Edit Distance (Levenshtein)
Mô tả nguyên lý
Tính số thao tác tối thiểu (chèn, xóa, thay thế) để biến đổi chuỗi này thành chuỗi khác.
Cài đặt mẫu (Implementation)
// Xây dựng bảng quy hoạch động 2 chiều so sánh từng ký tự của hai chuỗi.
Egg Dropping Problem
Mô tả nguyên lý
Tìm số lần thử tối thiểu để xác định tầng cao nhất mà quả trứng không bị vỡ.
Cài đặt mẫu (Implementation)
// Bài toán quy hoạch động tối ưu hóa số tầng và số quả trứng.
Fibonacci (DP - Tabulation)
Mô tả nguyên lý
Tính số Fibonacci bằng phương pháp quy hoạch động hướng lên (Bottom-up).
Cài đặt mẫu (Implementation)
function fibDP($n) {
if ($n <= 1) return $n;
$dp = [0, 1];
for ($i = 2; $i <= $n; $i++) {
$dp[$i] = $dp[$i-1] + $dp[$i-2];
}
return $dp[$n];
}
Kadane Algorithm
Mô tả nguyên lý
Tìm tổng mảng con liên tiếp lớn nhất trong mảng số nguyên.
Cài đặt mẫu (Implementation)
function maxSubArray($nums) {
$maxCurrent = $maxGlobal = $nums[0];
for ($i = 1; $i < count($nums); $i++) {
$maxCurrent = max($nums[$i], $maxCurrent + $nums[$i]);
if ($maxCurrent > $maxGlobal) $maxGlobal = $maxCurrent;
}
return $maxGlobal;
}
Knapsack Problem (0/1)
Mô tả nguyên lý
Bài toán cái túi cổ điển: chọn các món đồ có trọng lượng và giá trị sao cho tổng giá trị lớn nhất.
Cài đặt mẫu (Implementation)
function knapsack($W, $wt, $val, $n) {
$dp = array_fill(0, $n + 1, array_fill(0, $W + 1, 0));
for ($i = 0; $i <= $n; $i++) {
for ($w = 0; $w <= $W; $w++) {
if ($i == 0 || $w == 0) $dp[$i][$w] = 0;
elseif ($wt[$i-1] <= $w) $dp[$i][$w] = max($val[$i-1] + $dp[$i-1][$w - $wt[$i-1]], $dp[$i-1][$w]);
else $dp[$i][$w] = $dp[$i-1][$w];
}
}
return $dp[$n][$W];
}
Longest Common Subsequence (LCS)
Mô tả nguyên lý
Tìm chuỗi con chung dài nhất của hai chuỗi ký tự.
Cài đặt mẫu (Implementation)
function lcs($X, $Y, $m, $n) {
$L = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 0; $i <= $m; $i++) {
for ($j = 0; $j <= $n; $j++) {
if ($i == 0 || $j == 0) $L[$i][$j] = 0;
elseif ($X[$i-1] == $Y[$j-1]) $L[$i][$j] = $L[$i-1][$j-1] + 1;
else $L[$i][$j] = max($L[$i-1][$j], $L[$i][$j-1]);
}
}
return $L[$m][$n];
}
Longest Increasing Subsequence (LIS)
Mô tả nguyên lý
Tìm độ dài chuỗi con tăng dần dài nhất trong một mảng số.
Cài đặt mẫu (Implementation)
function lis($arr) {
$n = count($arr);
if ($n == 0) return 0;
$dp = array_fill(0, $n, 1);
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($arr[$i] > $arr[$j]) $dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
return max($dp);
}
Matrix Chain Multiplication
Mô tả nguyên lý
Tìm thứ tự nhân ma trận tối ưu sao cho tổng số phép nhân scalar là ít nhất.
Cài đặt mẫu (Implementation)
// Quy hoạch động khoảng cách (matrix chain order).
Subset Sum Problem
Mô tả nguyên lý
Xác định xem có tồn tại tập con của mảng có tổng bằng một giá trị cho trước hay không.
Cài đặt mẫu (Implementation)
// Kiểm tra khả năng tạo tổng bằng cách duyệt qua từng phần tử.