Thuật toán quy hoạch động trong C++ và các bài tập (Full Code)

Thuật toán Quy hoạch động (Dynamic Programming) là một kỹ thuật trong lập trình và toán học giúp giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Dưới đây là một số điểm chính về thuật toán này:

Bài toán con gối nhau: Quy hoạch động được sử dụng khi các bài toán con được gọi đi gọi lại nhiều lần. Thay vì tính toán lại mỗi lần, kết quả của các bài toán con này được lưu trữ và sử dụng lại, giúp tiết kiệm thời gian tính toán.

Cấu trúc con tối ưu: Bài toán lớn có thể được giải quyết bằng cách kết hợp các lời giải của các bài toán con. Điều này có nghĩa là lời giải của bài toán lớn phụ thuộc vào lời giải của các bài toán con.

Các bước thực hiện:

– Xác định cấu trúc của bài toán con tối ưu: Hiểu cách bài toán lớn được chia thành các bài toán con và cách kết quả của chúng kết hợp lại để giải quyết bài toán lớn.

– Định nghĩa hàm hồi quy: Xác định công thức hoặc hàm hồi quy để giải quyết bài toán dựa trên các bài toán con.

– Tính giá trị của bài toán con theo thứ tự từ nhỏ đến lớn: Bắt đầu từ những bài toán con nhỏ nhất và sử dụng công thức hồi quy để tính giá trị của các bài toán con lớn hơn.

– Lưu trữ kết quả của các bài toán con: Kết quả của mỗi bài toán con được lưu trữ để sử dụng lại sau này. Quy hoạch động là một kỹ thuật mạnh mẽ và hiệu quả, đặc biệt hữu ích trong các cuộc thi lập trình và giải quyết các bài toán tối ưu phức tạp.

Bài tập thực hành

Bài 1. Dãy Fibonacci

Bài toán về dãy Fibonacci là một trong những ví dụ cơ bản và điển hình khi học về thuật toán quy hoạch động. Dãy Fibonacci được định nghĩa như sau:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) với n >= 2

Dưới đây là cách tiếp cận bằng quy hoạch động để tính số Fibonacci thứ n.

Sử dụng mảng dp để lưu trữ giá trị của các số Fibonacci từ F(0) đến F(n).
Khởi tạo dp[0] = 0 và dp[1] = 1.
Sử dụng vòng lặp để tính các số Fibonacci tiếp theo dựa trên công thức:

dp[i] = dp[i-1] + dp[i-2]

Code tham khảo:

Vector:

#include <iostream>
#include <vector>

using namespace std;

int fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    vector<int> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;
    cout << "Số Fibonacci thứ " << n << ": " << fibonacci(n) << endl;
    return 0;
}

Mảng:

#include <iostream>

using namespace std;

int fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    int dp[1000];  // Giả sử kích thước tối đa là 1000
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;
    cout << "Số Fibonacci thứ " << n << ": " << fibonacci(n) 
    
    return 0;
}

Liệt kê dãy Fibonacci:

Vector:

#include <iostream>
#include <vector>

using namespace std;

vector<int> fibonacciSequence(int n) {
    if (n <= 0) return {};

    vector<int> dp(n, 0);
    dp[0] = 1;
    if (n > 1) dp[1] = 1;

    for (int i = 2; i < n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp;
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;
    
    vector<int> fibSequence = fibonacciSequence(n);
    
    cout << "Dãy Fibonacci từ 1 đến " << n << " là: ";
    for (int num : fibSequence) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Mảng:

#include <iostream>

using namespace std;

void fibonacciSequence(int n, int* dp) {
    if (n <= 0) return;

    dp[0] = 1;
    if (n > 1) dp[1] = 1;

    for (int i = 2; i < n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;

    if (n > 0) {
        int dp[1000];  // Giả sử kích thước tối đa là 1000
        fibonacciSequence(n, dp);

        cout << "Dãy Fibonacci từ 1 đến " << n << " là: ";
        for (int i = 0; i < n; ++i) {
            cout << dp[i] << " ";
        }
        cout << endl;
    } else {
        cout << "n phải lớn hơn 0." << endl;
    }

    return 0;
}

Bài 2. Dãy con đơn điệu dài nhất (Longest Increasing Subsequence):

Mô tả: Tìm dãy con tăng dài nhất trong một dãy số cho trước.

Ví dụ: Dãy số [10, 22, 9, 33, 21, 50, 41, 60, 80] có dãy con tăng dài nhất là [10, 22, 33, 50, 60, 80].

Trường hợp chỉ tìm độ dài của dãy con tăng dài nhất:

Vector:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm tìm độ dài dãy con tăng dài nhất
int longestIncreasingSubsequence(vector<int>& nums) {
    if (nums.empty()) return 0; // Nếu dãy số rỗng, trả về 0

    vector<int> dp(nums.size(), 1); //Khởi tạo mảng dp = giá trị 1

    // Duyệt qua từng phần tử của dãy số
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            // Nếu phần tử hiện tại lớn hơn phần tử trước đó
            if (nums[i] > nums[j]) {
                // Cập nhật giá trị dp[i] nếu tìm thấy
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // Trả về độ dài lớn nhất của dãy con tăng
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> nums = {10, 22, 9, 33, 21, 50, 41, 60, 80}; // Dãy số đầu vào
    cout << "Độ dài dãy con tăng dài nhất là: " << longestIncreasingSubsequence(nums) << endl; // Xuất kết quả
    return 0;
}

Mảng:

#include <iostream>
#include <algorithm>

using namespace std;

// Hàm tìm độ dài dãy con tăng dài nhất
int longestIncreasingSubsequence(int nums[], int n) {
    if (n == 0) return 0; // Nếu dãy số rỗng, trả về 0

    int dp[n]; // Khởi tạo mảng dp
    fill(dp, dp + n, 1); // Gán giá trị 1 cho các phần tử của dp

    // Duyệt qua từng phần tử của dãy số
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            // Nếu phần tử hiện tại lớn hơn phần tử trước đó
            if (nums[i] > nums[j]) {
                // Cập nhật giá trị dp[i] 
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // Trả về độ dài lớn nhất của dãy con tăng
    return *max_element(dp, dp + n);
}

int main() {
    int nums[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}; 
    int n = sizeof(nums) / sizeof(nums[0]); // Số lượng phần tử
    cout << "Độ dài dãy con tăng dài nhất là: " << longestIncreasingSubsequence(nums, n) << endl; // Xuất kết quả
    return 0;
}

Trường hợp lấy độ dài và liệt kê dãy con tăng dài nhất:

Vector:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm tìm độ dài và liệt kê dãy con tăng dài nhất
vector<int> longestIncreasingSubsequence(vector<int>& nums) {
    if (nums.empty()) return {};

    int n = nums.size();
    vector<int> dp(n, 1), prev(n, -1);
    int maxLength = 1, endIndex = 0;

    // Duyệt qua từng phần tử của dãy số
    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;
                prev[i] = j;
            }
        }
        if (dp[i] > maxLength) {
            maxLength = dp[i];
            endIndex = i;
        }
    }

    // Truy vết lại dãy con tăng dài nhất
    vector<int> lis;
    for (int i = endIndex; i >= 0; i = prev[i]) {
        lis.push_back(nums[i]);
        if (prev[i] == -1) break;
    }
    reverse(lis.begin(), lis.end());

    return lis;
}

int main() {
    vector<int> nums = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    vector<int> lis = longestIncreasingSubsequence(nums); 

    cout << "Dãy con tăng dài nhất là: ";
    for (int num : lis) {
        cout << num << " ";
    }
    cout << endl;

    return 0;

Mảng:

#include <iostream>
#include <algorithm>

using namespace std;

void longestIncreasingSubsequence(int nums[], int n) {
    if (n == 0) return;

    int dp[n], prev[n];
    fill(dp, dp + n, 1);
    fill(prev, prev + n, -1);

    int maxLength = 1, endIndex = 0;

    // Duyệt qua từng phần tử của dãy số
    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;
                prev[i] = j;
            }
        }
        if (dp[i] > maxLength) {
            maxLength = dp[i];
            endIndex = i;
        }
    }

    // Truy vết lại dãy con tăng dài nhất
    int lis[maxLength];
    int index = maxLength - 1;
    for (int i = endIndex; i >= 0; i = prev[i]) {
        lis[index--] = nums[i];
        if (prev[i] == -1) break;
    }

    // Xuất kết quả
    cout << "Dãy con tăng dài nhất là: ";
    for (int i = 0; i < maxLength; ++i) {
        cout << lis[i] << " ";
    }
    cout << endl;
    cout << "Tổng số phần tử của dãy con tăng dài nhất là: " << maxLength << endl;
}

int main() {
    int nums[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}; 
    int n = sizeof(nums) / sizeof(nums[0]); // Số lượng phần tử    longestIncreasingSubsequence(nums, n); // Tìm và liệt kê 
    return 0;
}

Bài 3. Bài toán balo (Knapsack Problem):

Mô tả: Cho một tập hợp các đồ vật, mỗi đồ vật có trọng lượng và giá trị. Tìm cách chọn các đồ vật để tối đa hóa giá trị mà không vượt quá trọng lượng cho phép.

Ví dụ: Với trọng lượng tối đa là 50, các đồ vật có trọng lượng [10, 20, 30] và giá trị [60, 100, 120], giá trị lớn nhất có thể đạt được là 220.

Tìm giá trị lớn nhất đạt được:

Vector:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // Duyệt qua từng đồ vật
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50; // Trọng lượng tối đa của balo
    vector<int> weights = {10, 20, 30}; // Trọng lượng các đồ vật
    vector<int> values = {60, 100, 120}; // Giá trị của các đồ vật
    int n = weights.size(); // Số lượng đồ vật

    cout << "Giá trị lớn nhất: " << knapsack(W, weights, values, n) << endl;
    return 0;
}

Mảng:

#include <iostream>
#include <algorithm>

using namespace std;

int knapsack(int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1];

    // Khởi tạo mảng dp
    for (int i = 0; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50; // Trọng lượng tối đa của balo
    int weights[] = {10, 20, 30}; // Trọng lượng của các đồ vật
    int values[] = {60, 100, 120}; // Giá trị của các đồ vật
    int n = sizeof(weights) / sizeof(weights[0]); // Số lượng

    cout << "Giá trị lớn nhất: " << knapsack(W, weights, values, n) << endl;
    return 0;
}

Liệt kê thêm các đồ vật được chọn:

Vector:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void knapsack (int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // Duyệt qua từng đồ vật
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // Truy vết lại các đồ vật được chọn
    int res = dp[n][W];
    cout << "Giá trị lớn nhất: " << res << endl;

    int w = W;
    cout << "Các đồ vật được chọn): " << endl;
    for (int i = n; i > 0 && res > 0; --i) {
        if (res != dp[i - 1][w]) {
            cout << weights[i - 1] << " " << values[i - 1] << endl;
            res -= values[i - 1];
            w -= weights[i - 1];
        }
    }
    cout << endl;
}

int main() {
    int W = 50; // Trọng lượng tối đa của balo
    vector<int> weights = {10, 20, 30}; // Trọng lượng các đồ vật
    vector<int> values = {60, 100, 120}; // Giá trị của các đồ vật
    int n = weights.size(); // Số lượng đồ vật

    knapsack(W, weights, values, n);
    return 0;
}

Mảng:

#include <iostream>
#include <algorithm>

using namespace std;

void knapsack (int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1];

    // Khởi tạo mảng dp
    for (int i = 0; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // Truy vết lại các đồ vật được chọn
    int res = dp[n][W];
    cout << "Giá trị lớn nhất: " << res << endl;

    int w = W;
    cout << "Các đồ vật được chọn: " << endl;
    for (int i = n; i > 0 && res > 0; --i) {
        if (res != dp[i - 1][w]) {
            cout << weights[i - 1] << " " << values[i - 1] << endl;
            res -= values[i - 1];
            w -= weights[i - 1];
        }
    }
    cout << endl;
}

int main() {
    int W = 50; // Trọng lượng tối đa của balo
    int weights[] = {10, 20, 30}; // Trọng lượng của các đồ vật
    int values[] = {60, 100, 120}; // Giá trị của các đồ vật
    int n = sizeof(weights) / sizeof(weights[0]); // Số lượng 

    knapsack(W, weights, values, n);
    return 0;
}

Bài tập tham khảo 1

Dãy con đơn điệu dài nhất: Tìm dãy con tăng dài nhất trong một dãy số cho trước.
Tổng lớn nhất của dãy con liên tiếp: Tìm tổng lớn nhất của một dãy con liên tiếp trong một dãy số.
Số cách phân tích một số thành tổng các số nhỏ hơn hoặc bằng nó: Tìm số cách phân tích một số ( n ) thành tổng của các số nhỏ hơn hoặc bằng ( n ).
Số cách để đạt được một tổng cho trước: Tìm số cách để đạt được một tổng ( S ) từ một tập hợp các số cho trước.
Số cách để leo cầu thang: Tìm số cách để leo lên bậc thang thứ ( n ) khi mỗi lần có thể bước 1 hoặc 2 bậc.
Số cách để xếp gạch: Tìm số cách để xếp gạch kích thước 1×2 và 2×1 để phủ kín một bảng 2xn.
Số cách để xếp ghế: Tìm số cách để xếp ghế màu sao cho không có hai ghế cùng màu đỏ đứng cạnh nhau.
Số cách để chia một dãy số thành các dãy con có tổng bằng nhau: Tìm số cách để chia một dãy số thành các dãy con có tổng bằng nhau.
Số cách để chọn các phần tử trong một dãy sao cho tổng của chúng bằng một giá trị cho trước: Tìm số cách để chọn các phần tử trong một dãy sao cho tổng của chúng bằng một giá trị cho trước.
Số cách để sắp xếp các phần tử trong một dãy sao cho không có hai phần tử liên tiếp giống nhau: Tìm số cách để sắp xếp các phần tử trong một dãy sao cho không có hai phần tử liên tiếp giống nhau.

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 1. Dãy con tăng dài nhất (LIS)
int LIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int max_len = 1;
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}

// 2. Tổng lớn nhất của dãy con liên tiếp (Kadane's Algorithm)
int maxSubArray(vector<int>& nums) {
    int max_sum = nums[0], current_sum = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        current_sum = max(nums[i], current_sum + nums[i]);
        max_sum = max(max_sum, current_sum);
    }
    return max_sum;
}

// 3. Số cách phân tích một số thành tổng các số nhỏ hơn hoặc bằng nó
int partitionNumber(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] += dp[j - i];
        }
    }
    return dp[n];
}

// 4. Số cách để đạt được một tổng cho trước
int countSumWays(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int num : nums) {
        for (int i = num; i <= target; ++i) {
            dp[i] += dp[i - num];
        }
    }
    return dp[target];
}

// 5. Số cách để leo cầu thang
int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 6. Số cách để xếp gạch
int tileWays(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 7. Số cách để xếp ghế không có 2 ghế đỏ cạnh nhau
int arrangeChairs(int n) {
    if (n == 1) return 2;
    vector<int> dp(n + 1);
    dp[1] = 2; dp[2] = 3;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 8. Số cách chia dãy số thành các dãy con có tổng bằng nhau
bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int i = target; i >= num; --i) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

// 9. Số cách chọn phần tử sao cho tổng bằng giá trị cho trước
int subsetSum(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int num : nums) {
        for (int i = target; i >= num; --i) {
            dp[i] += dp[i - num];
        }
    }
    return dp[target];
}

// 10. Số cách sắp xếp dãy không có 2 phần tử liên tiếp giống nhau
int countArrangements(int n, int k) {
    if (n == 1) return k;
    int same = 0, diff = k;
    for (int i = 2; i <= n; ++i) {
        int temp = diff;
        diff = (same + diff) * (k - 1);
        same = temp;
    }
    return same + diff;
}

Bài tập tham khảo 2

Bài toán chia kẹo: Cho một dãy số đại diện cho số lượng kẹo trong mỗi túi, tìm cách chia các túi kẹo thành hai nhóm sao cho tổng số kẹo trong hai nhóm là bằng nhau.
Bài toán xếp gạch tối ưu: Tìm số cách xếp gạch kích thước 1×2 và 2×1 để phủ kín một bảng 2xn sao cho số lượng gạch 1×2 là tối thiểu.
Bài toán chọn số tối ưu: Cho một dãy số, tìm cách chọn một số lượng phần tử sao cho tổng của chúng là lớn nhất nhưng không có hai phần tử nào đứng cạnh nhau.
Bài toán phân tích số thành tổng các số nguyên tố: Tìm số cách phân tích một số ( n ) thành tổng của các số nguyên tố.
Bài toán xếp ghế nâng cao: Tìm số cách xếp ghế màu sao cho không có hai ghế cùng màu đỏ đứng cạnh nhau và tổng số ghế là tối đa.
Bài toán chọn phần tử tối ưu với điều kiện: Cho một dãy số, tìm cách chọn các phần tử sao cho tổng của chúng là lớn nhất và không có hai phần tử nào có chỉ số chênh lệch nhỏ hơn ( k ).
Bài toán phân tích số thành tổng các số lẻ: Tìm số cách phân tích một số ( n ) thành tổng của các số lẻ.
Bài toán chọn phần tử tối ưu với trọng số: Cho một dãy số và một dãy trọng số tương ứng, tìm cách chọn các phần tử sao cho tổng trọng số là lớn nhất nhưng không có hai phần tử nào đứng cạnh nhau.
Bài toán xếp gạch tối ưu với điều kiện: Tìm số cách xếp gạch kích thước 1×2 và 2×1 để phủ kín một bảng 2xn sao cho số lượng gạch 2×1 là tối thiểu.
Bài toán chọn phần tử tối ưu với giới hạn: Cho một dãy số và một giới hạn ( L ), tìm cách chọn các phần tử sao cho tổng của chúng là lớn nhất nhưng không vượt quá ( L ).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// 1. Bài toán chia kẹo
bool canPartitionCandies(vector<int>& candies) {
    int sum = accumulate(candies.begin(), candies.end(), 0);
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int candy : candies) {
        for (int i = target; i >= candy; --i) {
            dp[i] = dp[i] || dp[i - candy];
        }
    }
    return dp[target];
}

// 2. Bài toán xếp gạch tối ưu
int minTileWays(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= n; ++i) {
        dp[i] = min(dp[i - 1] + 1, dp[i - 2] + 1);
    }
    return dp[n];
}

// 3. Bài toán chọn số tối ưu
int maxSumNoAdjacent(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];
    int incl = nums[0], excl = 0;
    for (int i = 1; i < nums.size(); ++i) {
        int new_excl = max(incl, excl);
        incl = excl + nums[i];
        excl = new_excl;
    }
    return max(incl, excl);
}

// 4. Phân tích số thành tổng các số nguyên tố
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int countPrimeSumWays(int n) {
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (isPrime(i)) primes.push_back(i);
    }
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int prime : primes) {
        for (int i = prime; i <= n; ++i) {
            dp[i] += dp[i - prime];
        }
    }
    return dp[n];
}

// 5. Xếp ghế nâng cao
int arrangeChairsAdvanced(int n) {
    if (n == 1) return 2;
    vector<int> dp(n + 1);
    dp[1] = 2; dp[2] = 3;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 6. Chọn phần tử tối ưu với điều kiện
int maxSumWithDistance(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = nums[i];
        for (int j = 0; j < i - k; ++j) {
            dp[i] = max(dp[i], dp[j] + nums[i]);
        }
    }
    return *max_element(dp.begin(), dp.end());
}

// 7. Phân tích số thành tổng các số lẻ
int countOddSumWays(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i += 2) {
        for (int j = i; j <= n; ++j) {
            dp[j] += dp[j - i];
        }
    }
    return dp[n];
}

// 8. Chọn phần tử tối ưu với trọng số
int maxWeightedSum(vector<int>& values, vector<int>& weights) {
    int n = values.size();
    int incl = weights[0], excl = 0;
    for (int i = 1; i < n; ++i) {
        int new_excl = max(incl, excl);
        incl = excl + weights[i];
        excl = new_excl;
    }
    return max(incl, excl);
}

// 9. Xếp gạch tối ưu với điều kiện
int minTileWays2(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = min(dp[i - 1] + 1, dp[i - 2] + 2);
    }
    return dp[n];
}

// 10. Chọn phần tử tối ưu với giới hạn
int maxSumWithLimit(vector<int>& nums, int limit) {
    vector<int> dp(limit + 1, 0);
    for (int num : nums) {
        for (int i = limit; i >= num; --i) {
            dp[i] = max(dp[i], dp[i - num] + num);
        }
    }
    return dp[limit];
}

CHÚC CÁC BẠN HỌC TỐT!

Lập trình C/C++

Thuật toán quy hoạch động trong C++ và các bài tập (Full Code)

Đỗ Thành