Dãy Con Có Tổng Bằng S

     

Đặt L = 1 nếu hoàn toàn có thể tạo ra tổng bằng t từ dãy con tất cả các thành phần nằm trong dãy từ A1 -> Ai và trái lại L = 0. Nếu như L = 1 thì ta có thể tạo ra dãy con có tổng bằng S từ A1 -> AN.

Bạn đang xem: Dãy con có tổng bằng s

Ta hoàn toàn có thể tính L theo công thức: L = 1 giả dụ L = 1 hoặc L> = 1.

Cài đặt:

Nếu áp dụng luôn luôn công thức bên trên ta bắt buộc dùng mảng 2 chiều. Ta có thể nhận xét rằng để hoàn toàn có thể tính mẫu thứ i, ta chỉ cần dòng i-1. Bảng phương pháp khi đó chỉ việc mảng một chiều L<0…S> và được tính như sau:

L = 0; L<0> = 1;

for (int i=1;i=a;t–)

if (L==0 && L> ==1) L = 1;

Dễ thấy độ phức hợp của cách thiết đặt là O(m), độ phức hợp của thuật toán là O(n*m), m là tổng của n số.


Share this:


Like this:


Like Loading...

Xem thêm: Hình Ảnh Chim Vành Khuyên Đẹp, Phân Biệt Vành Khuyên Trống, Mái Bằng Hình Ảnh


*

Published by nguyensontung25051995


View all posts by nguyensontung25051995


May 31, 2017

Quy hoạch động, Uncategorized

Post navigation


Xâu nhỏ chung dàinhất
Cách thêm tên miền ảo cho localhost vớiXAMPP

Leave a Reply Cancel reply


Enter your comment here...

Fill in your details below or click an icon khổng lồ log in:


*

Email (required) (Address never made public)
Name (required)
Website
*

You are commenting using your acsregistrars.vn.com account.(LogOut/Change)


*

You are commenting using your Twitter account.(LogOut/Change)


*

You are commenting using your Facebook account.(LogOut/Change)


Cancel

Connecting to lớn %s


Notify me of new comments via email.

Notify me of new posts via email.

Xem thêm: Vẽ Tranh Vẽ Về Quê Hương Đơn Giản Dễ Vẽ Mà Đẹp, 56+ Vẽ Tranh Quê Hương Phong Cảnh Đơn Giản Mà Đẹp


Δ


Start a Blog at acsregistrars.vn.com.

Up ↑


Privacy và Cookies: This site uses cookies. By continuing lớn use this website, you agree lớn their use. To find out more, including how khổng lồ control cookies, see here:Cookie Policy
FollowFollowing
Sign me up
%d bloggers like this: