Đếm số cách biểu diễn N dưới dạng tổng của 1, 3 và 4 trong C++

Cho một số dương N đầu vào. Mục tiêu: tìm số cách biểu diễn N dưới dạng tổng của các số 1, 3 và 4. Ví dụ: N = 4 → 1+1+1+1, 3+1, 1+3, 4 → 4 cách.

Hiểu qua ví dụ

Đầu vào: N = 5

Đầu ra: Số cách biểu diễn: 6

Giải thích: 5 = 1+1+1+1+1, 1+3+1, 3+1+1, 1+1+3, 4+1, 1+4.

Đầu vào: N = 6

Đầu ra: Số cách biểu diễn: 9

Giải thích: 6 = 1+1+1+1+1+1, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 3+3, 4+1+1, 1+4+1, 1+1+4.

Phương pháp sử dụng

Sử dụng quy hoạch động. Mảng arr[i] với i là số và arr[i] là số cách biểu diễn.

Trường hợp cơ sở:

• arr[0] = 1 (1 cách - không dùng số nào)
• arr[1] = 1 (chỉ 1)
• arr[2] = 1 (chỉ 1+1)
• arr[3] = 2 (1+1+1, 3)

Các số khác: arr[i] = arr[i-1] + arr[i-3] + arr[i-4].

• Nhập số dương N.
• Hàm Expres_sum(int N) trả về số cách.
• Mảng arr[N+1] lưu số cách.
• Khởi tạo cơ sở: arr[0]=1, arr[1]=1, arr[2]=1, arr[3]=2.
• Duyệt i = 4 đến N: arr[i] = arr[i-1] + arr[i-3] + arr[i-4].
• Trả về arr[N].

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

int Expres_sum(int N) { 
    int arr[N + 1]; 
    arr[0] = 1; 
    arr[1] = 1; 
    arr[2] = 1; 
    arr[3] = 2; 
    for (int i = 4; i <= N; i++) { 
        arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4]; 
    } 
    return arr[N]; 
} 

int main() { 
    int N = 5; 
    cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of different ways to express N as the sum of 1, 3 and 4 are: 6