Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


adm

Đăng ký: 20-05-2017
Offline Đăng nhập: 29-05-2018 - 21:15
-----

Bài viết của tôi gửi

Trong chủ đề: Hỏi 1 chút về thuật toán lập trình

21-05-2017 - 23:43



nếu cướp nhà i thì f[i] =f[i-2] +a[i] cái f[i-2] nó đâu tính cái a[i-1] nên vẫn thỏa mãn điều kiện k có 2 nhà cạnh nhau còn gì

à. ý bác là tính dãy chẵn dãy lẻ ý ạ

nếu zậy sẽ có trường hợp bị sót như sau

$array = [10000,3,5,6];

nó chỉ xét dãy lẻ. hay chẵn. thành ra bị bỏ xót


Trong chủ đề: Hỏi 1 chút về thuật toán lập trình

21-05-2017 - 22:34



bạn làm theo phương pháp quy hoạch động

gọi a[i] là số tiền cướp được ở nhà i

f[i] là số tiền maxx khi cướp i nhà đầu tiên

+, nếu không cướp nhà i thì f[i]= f[i-1]

+, nếu cướp nhà i thì f[i]= f[i-2] +a[i]

vì ta cần số tiền cướp được là lớn nhất nên

f[i]= max(f[i-1],f[i-2]+a[i])

đầu tiên khởi tạo f[0]=0;

f[1]=a[1]

kết quả của chúng là chính là f[n]

Bác êi. ta không cướp được 2 nhà cạnh nhau nhá. nếu kiểu quy hoạch động này với mảng 4 số thì rất dễ đạp phải 1,2,4 bác ạ