01/10/2018, 08:15
Thắc mắc về bài toán dãy con có tổng bằng S
Em nghĩ hoài nhưng vẫn không hiểu chổ này: “Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.”
Mấy anh chị có thể giải thích giúp em không?? em yếu QHĐ lắm ạ :((
Bài liên quan
Bởi nếu dùng for to giả sử L[t]=1 thì sẽ dẫn đến L[t+a[i]]=1,L[t+a[i]+a[i]]=1… Do for to,a[i] dc sử dụng nhiều hơn 1 lần. Còn for down to để hình thành tổng t, a[i] chỉ sử dụng 1 lần Bởi t-a[i] trước đó đã có và a[i]
nhưng nếu mình xài công thức trên ảnh nhưng dùng for to thì sẽ sai ở chỗ nào ạ?
Như giải thích ở trên thì for to cũng sẽ hình thành tổng S nhưng a[i] có thể sử dụng nhiều lần, trong khi đề bài là a[i] chỉ dùng tối đa 1 lần
Bỏi vì để có những slot phía sau thì phải có slot đầu vì vậy phải tính từ lớn đến bé.
p/s: làm như vầy sẽ là O(n*delta_S) time và O(delta_S) space với delta_S =
sum+(a)-sum-(a)