วีดีโอ

@@thietvu7486 em xin thầy 😩😩

lâu rồi sorry mình k còn giữ ấy b

để trả lời được câu hỏi này mình cần trả lời được câu hỏi tại sao người ta lại nghĩ ra cách lấy 1 vector và thêm các giá trị vào vector đó đồng thời đảm bảo thứ tự tăng dần của vector

xét vị trí i ứng với giá trị a[i] của mảng ban đầu , mình mong muốn sẽ biết được độ dài lớn nhất của dãy tăng dần kết thúc bởi giá trị a[i] này , hiển nhiên mình sẽ tìm xem phía trước có dãy nào có kết thúc nhỏ hơn a[i] và có độ dài tốt nhất có thể để đem nối vào a[i] hay không , =>> mình cần có 1 vector ( hoặc có thể dùng Set hoặc Map) nhằm lưu trữ các giá trị riêng biệt và có thể biết được độ dài lớn nhất của dãy có kết thúc là giá trị riêng biệt đó , ví dụ [1,3,5,7,9] như trong video sẽ giúp mình biết được độ dài lớn nhất của dãy có kết thúc là 1 là 1 , kết thúc là 3 là 2 , kết thúc là 5 là 3 ,...

trường hợp giá trị 6 phải thay vào là trường hợp bạn nhắc tới , câu hỏi là chuyện gì xảy ra nếu mình không thay thế số 7 bởi số 6 , vector hiện tại là [1,3,5,7,9] , a[i] đang xét = 6 và mình cần đặt ra câu hỏi tại sao cần chạy vào vector để tìm giá trị đầu tiên lớn hơn 6 ( số 7) và thay 7 thành 6

buộc phải thay 7 bởi 6 như vậy bởi xảy ra tình huống như thế này , giả sử có thêm 1 số phần tử nằm phía sau ( mình mở rộng bài toán để dễ minh họa) , giả sử phần tử đó là a[1000] = 1001 , mình cần tìm trong vector xem dãy nào có kết thúc nhỏ hơn 1001 và có độ dài lớn nhất không , nếu không thay 7 bởi 6 sẽ dẫn tới tình huống giá trị trong vector tuy nhỏ hơn nhưng lại có độ dài lớn hơn ( dãy A có kết thúc là 6 nhưng lại dài hơn dãy có kết thúc là 7 ) , khi này đứng vị trí có a[i] = 1001 mình không thể biết được đâu mới là dãy có kết thúc nhỏ hơn nhưng có độ dài lớn nhất để nối vào ( lúc này buộc check từng giá trị 6 và 7 để so sánh và cập nhật kết quả =>> đi check từng giá trị như thế độ phức tạp nâng lên n^2) , do vậy mình xóa sổ thằng 7 khỏi các giá trị riêng biệt trong vector luôn , bởi 2 dãy tăng dần có cùng độ dài , 1 dãy có kết thúc là 6 và 1 dãy có kết thúc là 7 chẳng tội gì phải giữ thông tin của thằng 7 để làm gì cả, xóa sổ thằng 7 sẽ tránh được tình huống phía trên và luôn đảm bảo cứ tìm ra phần tử đầu tiên nhỏ hơn a[i] thì độ dài dãy kết thúc bởi phần tử đó 100% là độ dài lớn nhất có kết thúc < a[i]

tui xin 1 đăng kí nhe hiuhiu

@@lamquangnhathuy bạn mô tả rõ hơn được không , mình chưa hình dung được

@@xuanhuy9283 hehe để lại mình xin 1 subribe nha hehe

cho anh xin 1 sub nha hihi

@@redevil079 bạn tham khảo các nguồn khác xem , khả năng của mình chỉ tới đó thôi

bạn nói chi tiết hơn đi bạn

@@b21dccn809-luongngocyen cái này bạn có thể tự tìm hiểu về nhân ma trận, bài toán tìm số fibo thứ N với N ~ 1e18 sẽ được giới thiệu đầu tiên khi học

nếu thế thì quy về bài toán dãy con có tổng bằng S rồi bạn , bạn biến thể 1 tí giờ không phải là tồn tại tổng = Si nữa ( true hoặc false ) mà là số phần tử ít nhất để tổng của chúng bằng Si với Si <= S ( mình đang nói trong ngữ cảnh bài dãy con có tổng = S) ,bạn xem lại video dãy con có tổng = S trên kênh mình có ấy

mình quên mất , nếu đề là thế thì phải lọc ra các giá trị phân biệt của mảng đề cho nha

em hiểu được cách nó hoạt động thì tự khắc sửa được , thử nhá

@@b21dccn809-luongngocyen cơ bản là em không tìm được một cái hàm có chức năng ngược lại với hàm lower_bound ấy ạ

@@b21dccn809-luongngocyen mình thêm thuộc tính greater<>() vào trong hàm low_bound đúng không anh

đề bài yêu cầu là tìm số tờ tiền ít nhất rồi thì làm sao thêm được điều kiện chọn đúng K tờ tiền được bạn , bạn mô tả rõ hơn giúp mình được không

@@b21dccn809-luongngocyen Ví dụ đề bài là: đếm số cách đổi một mệnh giá tiền S chỉ sử dụng k tờ tiền

Đổi tiền như thế thì = bài toán dãy con có tổng = S rồi bạn , bạn hiểu bài dãy con có tổng = S thì bạn sửa 1 chút là được ( sửa biến đánh dấu 0 với 1 thành số cách chọn )

Đệ quy quay lui cũng là quy hoạch động mà em , quy hoạch động có 2 cách tiếp cận 1 là top-down 2 là bottom-up , trong video của anh là 1 trong 2 cách ấy

chả có tý đệ quy cũng chả có tý quay lui nào, xây dựng bảng công thức 100%

@@BaoTran-pv5kd bạn nên tìm hiểu thêm về các style code dp nha 🫶🏾

7+4=11>8

=))

Mấy nữa a tranh thủ làm nha 🥊

Qhd ít khi truy vết lắm b , nên mình cũng ít gặp dạng đó

Sr mình không bạn ạ , có bài nào hay bạn có thể trao đổi với mình qua fb nhé 🥰

Bạn để ý trong video mình có nói là các số a[i] luôn DƯƠNG , khi đó dp ở vị trí 4 chắc chắn lớn hơn dp ở vị trí 2, bởi vì dp 4 được tạo từ a4+ max(dp2,dp1), xảy ra 2 trường hợp , 1 là dp2 lớn hơn dp1, khi đó dp4= a4+ dp2, hiển nhiên dp4 chắc chắn lớn hơn dp2

Trường hợp còn lại dp4 được tạo thành từ a4+ dp1, điều này chứng tỏ dp2 < dp1( do nhỏ hơn nên mới không được chọn) =>> thằng dp2 sẽ k được tham gia vào phép tính dp6

Cả 2 trường hợp đều chứng tỏ dp2 không thể được chọn , dp3 và dp4 sẽ bao quát hơn

Mình bổ sung thêm , mình đã định nghĩa dp[i] là dãy con thoả mãn lớn nhất từ đầu tới vị trí i ,sau đó là trường hợp cơ sở qhd , thử hỏi với i= 2 và i =4 dp nào sẽ lớn hơn ?

Nếu dp2 > dp4 thì mình sẽ phát biểu là : dãy con lớn nhất thoả mãn từ đầu tới vị trí 2 sẽ lớn hơn dãy con lớn nhất thoả mãn từ đầu tới vị trí 4, bạn thấy có lí hay vô lí

n = 10 ^9 mình chịu bạn ạ

n = 10 ^ 5 vẫn có thể tính tổ hợp ckn nhưng bằng cách khác (nlogn do có dính dáng tới nghịch đảo modulo)

dạng này nó hơi nâng cao nên kiến thức nền phải vững mới ổn bạn ạ , + mình code đệ quy nên bạn khó hiểu cũng phải @_@

bạn xem lại 2 video phía trước phần QHD thử xem , nó có liên quan đến bài này á

Mình cảm ơn 🥰

Hi mình cảm ơn 🥰