Đến nội dung

Hình ảnh

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

- - - - -

  • Please log in to reply
Chủ đề này có 5 trả lời

#1
adm

adm

    Lính mới

  • Thành viên mới
  • 3 Bài viết

Giả sử em là một tên trộm chuyên đi cắp đồ. em có một dãy số là số tiền trong từng nhà ở một khu dân cư và chuẩn bị đi chôm. Và em biết rằng nếu đi chôm 2 nhà liền kề nhau thì chuông báo động sẽ kêu. Hỏi cách nào để chôm được nhiều tiền nhất ạ

Bài toán nguyên văn tiếng Anh:

You are planning to rob houses on a specific street, and you know that every house on the street has a certain amount of money hidden. The only thing stopping you from robbing all of them in one night is that adjacent houses on the street have a connected security system. The system will automatically trigger an alarm if two adjacent houses are broken into on the same night.

Given a list of non-negative integers nums representing the amount of money hidden in each house, determine the maximum amount of money you can rob in one night without triggering an alarm.

Em cảm ơn ạ


My email: [email protected]

My Facebook ID: airforceonecoder


#2
khgisongsong

khgisongsong

    Trung sĩ

  • Thành viên
  • 103 Bài viết

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ài viết đã được chỉnh sửa nội dung bởi khgisongsong: 21-05-2017 - 00:04

$\frac{(x!)^2.(-1)^x+1}{2x+1}\in Z $ (với $x\in N)<=>2x+1$ là số nguyên tố


#3
adm

adm

    Lính mới

  • Thành viên mới
  • 3 Bài viết


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 ạ


My email: [email protected]

My Facebook ID: airforceonecoder


#4
khgisongsong

khgisongsong

    Trung sĩ

  • Thành viên
  • 103 Bài viết

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ì


$\frac{(x!)^2.(-1)^x+1}{2x+1}\in Z $ (với $x\in N)<=>2x+1$ là số nguyên tố


#5
adm

adm

    Lính mới

  • Thành viên mới
  • 3 Bài viết


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


My email: [email protected]

My Facebook ID: airforceonecoder


#6
khgisongsong

khgisongsong

    Trung sĩ

  • Thành viên
  • 103 Bài viết

không phải dãy chẵn lẻ nếu mảng của bạn như thế thì nó sẽ chạy lần lượt như này

f[0]=0;

f[1]=10000;

f[2]= max(f[0]+3; f[1]) = 10000             // lấy max của f[1] và f[0] +3 

f[3] = max (f[1] +5 ; f[2]) =10005         // lấy max của f[1] +5 =10005 và f[2]=10000

f[4]= max(f[2] +6 ; f[3] ) = 10006         //vì f[2] + 6=10006 còn f[3] = 10005

vậy kết quả là 10006 lấy nhà 1 và nhà 4 chứ không phải như bạn nghĩ là nó lấy 2 với 4 hay 1 với 3


$\frac{(x!)^2.(-1)^x+1}{2x+1}\in Z $ (với $x\in N)<=>2x+1$ là số nguyên tố





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh