Quy hoạch động (DP)

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 10)

Quy hoạch động (DP)

Coin Change Problem

Thời gian (Time) O(amount * n)
Không gian (Space) O(amount)

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];
}
Quy hoạch động (DP)

Edit Distance (Levenshtein)

Thời gian (Time) O(m * n)
Không gian (Space) O(m * n)

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.
Quy hoạch động (DP)

Egg Dropping Problem

Thời gian (Time) O(n * k)
Không gian (Space) O(n * k)

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.
Quy hoạch động (DP)

Fibonacci (DP - Tabulation)

Thời gian (Time) O(n)
Không gian (Space) O(n)

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];
}
Quy hoạch động (DP)

Kadane Algorithm

Thời gian (Time) O(n)
Không gian (Space) O(1)

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;
}
Quy hoạch động (DP)

Knapsack Problem (0/1)

Thời gian (Time) O(nW)
Không gian (Space) O(nW)

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];
}
Quy hoạch động (DP)

Longest Common Subsequence (LCS)

Thời gian (Time) O(m * n)
Không gian (Space) O(m * n)

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];
}
Quy hoạch động (DP)

Longest Increasing Subsequence (LIS)

Thời gian (Time) O(n²)
Không gian (Space) O(n)

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);
}
Quy hoạch động (DP)

Matrix Chain Multiplication

Thời gian (Time) O(n³)
Không gian (Space) O(n²)

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).
Quy hoạch động (DP)

Subset Sum Problem

Thời gian (Time) O(sum * n)
Không gian (Space) O(sum)

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ử.