Phân tích một số thành tổng các số của dãy Fibonacci

[nguyenhieuckt (nguyenhieu)]

Đề :Phân tích một số nguyên dương thành tổng các số hạng của dãy
Fibonaci sao cho ít số hạng nhất.
Dữ liệu vào:
Số nguyên n (0<n<10^6)
Kết quả ra:
Các số hạng thuộc dãy Fibonaci theo thứ tự giảm dần mỗi số cách nhau 1 khoảng
trống.
Ý tưởng của em: em tạo một dãy fibo bé hơn n sau đó em quy hoạch động tìm tổng các số có tổng bằng n, nhưng không được điểm nào. Vì sao ạ ?

[rogp10]

Số trong dãy Fibo thì cứ trừ ra từ từ là 100% (aka greedy). https://en.wikipedia.org/wiki/Fibonacci_coding

Ngoài ra dãy {1, 2, 5}*10^k cũng là dãy greedy nổi tiếng.

[tntxtnt]

vì sao ai mà biết :V Quy hoạch động em test thế nào? Code ra sao? :V

[nguyenhieuckt (nguyenhieu)]

code đây ạ

#include <bits/stdc++.h>

using namespace std;
int j,i,x,a[100005],f[1005][1005],k;
int main()
{
    cin>>x;
    a[1]=1;
    i=1;
    while(a[i]<=x)
    {
        i++;
        a[i]=a[i-2]+a[i-1];
    }
    for(j=0;j<i;j++) f[j][0]=0;
    for(j=0;j<=x;j++) f[0][j]=0;
    for(j=1;j<i;j++)
        for(k=1;k<=x;k++)
    {
        if(a[j]>k)
            f[j][k]=f[j-1][k];
        else
            f[j][k]=max(f[j-1][k],f[j-1][k-a[j]]+a[j]);
    }
    cout<<f[i-1][x]<<endl;
    j=i-1; k=x;
    while(f[j][k]>0)
    {
        if(f[j][k]==f[j-1][k-a[j]]+a[j])
        {
            cout<<a[j]<<" ";

            k=k-a[j];
        }
            j--;
    }
}