ai bik giải bài này giúp mình với

[QuyNam]

Cho dãy số gồm n phần tử : a1,a2,a3,.....,an
Gọi S là tổng các số trong dãy và số K thỏa : 0<K<S
Hãy tính số cách lấy ra trong dãy các phần tử có tổng bằng K.

mình nghĩ bài này dùng quy hoạch động nhưng tìm mãi ko ra công thức truy hồi :glare:. Ai giúp với

[mini_bestboy]

Theo mình , công thức truy hồi là vầy :
F(m,T) = Tổng( F(m-1,T-a[i]) ), 0<i<=N
Với số có m phần tử chọn từ dãy đã cho có tổng là T. Kết quả cuối cùng cần tìm là F(n,k)

[QuyNam]

mình ko hiểu lắm, bạn giải thích rõ hơn dc ko

[bumzunpilo]

Theo mình , công thức truy hồi là vầy :
F(m,T) = Tổng( F(m-1,T-a[i]) ), 0<i<=N
Với số có m phần tử chọn từ dãy đã cho có tổng là T. Kết quả cuối cùng cần tìm là F(n,k)



anh ơi, cho em hỏi, làm cách nào mà anh tìm được công thức truy hồi za, em thấy nó... không đơn giản cho lắm:D (em k nói đến cái công thức trên của anh)

[mini_bestboy]

À, công thức của mình là vầy, Gọi F[i,j] là một phần tử bất kỳ trong hàm QHĐ trên thì i là số phần tử tối đa được chọn và j là Tổng của i phần tử đó.Vậy thì số cách chọn có i-1 phần tử sẽ có giá trị bằng cách loại bỏ một trong các phần tử trong dãy số trên. Do đó, CT là F[i,j]:=Tổng(F[i-1,j-A[k]) với 0<k<=N.

Mà mình nhầm, cái công thứ trên của mình là tìm hoán vị của các phần tử đó , mà trong khi cái đề yêu cầu là tìm tổ hợp thì phải, rồi nó còn lặp phần tử nửa chứ, ai pro QHĐ hơn thì tìm giùm mình cách bỏ hoán vị và bỏ lặp lại với.