Giá trị tối đa với lựa chọn chia hoặc giữ nguyên trong C++

Cho một số N. Nhiệm vụ: tìm giá trị tối đa bằng cách hoặc lấy giá trị như nguyên bản, hoặc chia thành các phần. Giá trị có thể trích xuất là F(N/2) + F(N/3) + F(N/4) + F(N/5).

Ví dụ

Đầu vào: N = 8

Đầu ra: 9

Giải thích

F(8) = F(8/2) + F(8/3) + F(8/4) + F(8/5)
     = F(4) + F(2) + F(2) + F(1)
     = 4 + 2 + 2 + 1 = 9

Phương pháp giải

Gọi đệ quy hàm cho các giá trị chia. Dùng quy hoạch động, tạo mảng lưu F(i) từ 0 đến N để tra cứu khi đệ quy.

Ví dụ

#include <iostream>
using namespace std;

int calcMaximumValue(int N) {
    int F[N + 1];
    int divVal = 0;
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <= N; i++) {
        divVal = (F[i / 2] + F[i / 3] + F[i / 4] + F[i / 5]);
        if (divVal > i)
            F[i] = divVal;
        else
            F[i] = i;
    }
    return F[N];
}

int main() {
    int N = 8;
    cout << "Giá trị tối đa với lựa chọn chia hoặc giữ nguyên = " << calcMaximumValue(N);
    return 0;
}

Đầu ra

Giá trị tối đa với lựa chọn chia hoặc giữ nguyên = 9