Một số bài về quy hoạch động cần giúp đỡ

[nncb2008]

Các bạn giúp mình giải một số bài này nhé
Bài 1:
Xoá xâu T một số kí tự thì được xâu con S. Hãy tìm xâu S3 có độ dài lớn nhất là xâu con của 2 xâu S1 và S2.
Bài 2:
Cho n số tự nhiên a1, a2,...,an và số nguyên K. Hãy đặt vào giữa các số ai phép toán cộng(+) hoặc trừ(-)(Không thay đổi thứ tự ai) để được phép tính có kết quả là K.
Bài 3: Cho xâu S hãy tìm xâu T thoả mãn: Đối xứng, chứa xâu S và ít kí tự nhất

[mr_invincible]

1/ Gọi F[i,j] là độ dài dãy con dài nhất chứa i phần tử đầu tiên của xâu S1 và j phần tử đầu tiên của xâu S2. Khi đó xảy ra 2 trường hợp:
- Nếu S1[i]=S2[j] thì f[i,j]=F[i-1,j-1]+1
- Nếu S1[i]<>S2[j] thì F[i,j]=max(F[i-1,j],F[i,j-1])

[mr_invincible]

3/ Nhận xét: Đề bài tương đương với việc thêm vào xâu S ít kí tự nhất để nó trở thành xâu đối xứng. Gọi F[i,j] là số kí tự ít nhất cần thêm vào để xâu S trở thành xâu đối xứng. Khi đó ta lần lượt tính F[i,i+k] với k chạy từ 0. Khi đó xảy ra 2 trường hợp
Nếu S[i]=S[i+k] thì F[i,i+k]=F[i+1,i+k-1]
Nếu S[i]<>S[i+k] thì F[i,i+k]=max(F[i+1,k],F[i,i+k-1)+1
việc còn lại khá dễ dàng, bạn chỉ cần lần theo mảng F để biết được các kí tự cần thêm là xong :D

[mr_invincible]

2/ Gọi B[i,k] là dấu cần đặt vào trước số thứ i để dãy a[1]...a[i] có tổng là k

[nncb2008]

Cảm ơn bạn nhé. Bài 2 và 3 mình vẫn chưa hiểu lắm.
To Admin: Sao không có nút "Thanks" nhỉ?

[nncb2008]

Bài 4: Một dây xích dài L đơn vị được nối với nhau bằng các đoạn xích có độ dài 1 đơn vị. Hỏi có bao nhiêu cách tháo các khớp nối để được các đoạn xích có độ dài
a, >= 1 đơn vị.
b, >= 2 đơn vị.

[nncb2008]

Có ai giúp bài 4 được không? Đang rất cần.

[nncb2008]

Bài 4:
Mình làm thế này không biết có đúng không, các bạn xem giúp mình nhé :
a, Gọi F(i) là số cách tháo các khớp nối đoạn xích dài i đơn vị để được các đoạn có độ dài >=1 đơn vị.
Xét các cách tháo được đoạn cuối cùng có độ dài >=1, sẽ có i cách tháo
Tháo đoạn cuối = 1 : Ta có F(i-1) cách
Tháo đoạn cuối = 2 : Ta có F(i-2) cách
...
Tháo đoạn cuối = i : Ta có F(0) cách
Và ta có F(0)=1, F(1)=1
Từ đó ta có : F(n)=F(0)+F(1)+F(2)+...+F(n-1)

[hhngocmai]

Moi nguoi chi cho minh ve chu de nay voi!