#1. Thuật Toán Quy Hoạch Động - Bài Toán Dãy Con Tăng Dài Nhất ( LIS)
Вставка
- Опубліковано 6 лют 2025
- Mở đầu chuỗi video về các bài toán kinh điển trong lập trình là bài toán quy hoạch động : Dãy con tăng dài nhất, các bạn có thể luyện tập các problem bên dưới :
Practice problem :
codeforces.com...
cses.fi/proble...
leetcode.com/p...
leetcode.com/p...
Các bạn đừng quên đăng kí kênh, like, chia sẻ video để ủng hộ mình có động lực lớn hơn để làm các tutorial miễn phí tới các bạn.
_____________________________________________
Các series lập trình :
Lập trình C++ : • Ngôn Ngữ Lập trình C++
Lập trình C : • Ngôn Ngữ Lập Trình C
Lý thuyết đồ thị : • Lý Thuyết Đồ Thị | Gra...
Java Collections and Trick : • Java Collections
Trò chuyện với 28tech : • Chia Sẻ Về Ngành Công ...
_____________________________________________
Liên hệ :
►Đăng ký học với mình tại : 28tech.com.vn
►Facebook chia sẻ kiến thức lập trình và thuật toán: / 28techandedu
►Facebook cá nhân : / andrew28042711
►Group : groups/28techgroup/
►Zalo / Phone : 0965303260
►Gmail: andrew168545824@gmail.com
© 2022 28tech
#28tech #ClassicProblem #DynamicProgramming #QHD
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Practice problem :
codeforces.com/problemsets/acmsguru/problem/99999/521
cses.fi/problemset/task/1145
leetcode.com/problems/longest-increasing-subsequence/
leetcode.com/problems/number-of-longest-increasing-subsequence/
link hackerrank nx a oi
Cảm ơn tác giả. rất hữu ích cho các bạn học sinh, sinh viên. Luôn ủng hộ kênh và chia sẻ cho các học trò
Em cảm ơn ạ
Mình đóng góp code Python cho bạn nào cần thì tham khảo nhé:
fi = open('lis.inp','r')
fo = open('lis.out','w')
n = int(fi.readline())
x = fi.readline().split()
A = [int(i) for i in x]
L = [1 for i in range(n)]
res = 1
for i in range(1,n):
for j in range(0,i):
if A[i] > A[j]:
L[i] = max(L[i],L[j]+1)
if L[i] > res: res = L[i]
fo.write(str(res))
fi.close()
fo.close()
n=[int(i) for i in input().split()]
s=[1]*len(n)
for i in range (1,len(n)):
for k in range (i):
if n[i]>n[k]:
s[i]=max(s[i],s[k]+1)
print(max(s))
tui ngắn hơn ông nè hehe
@@kiennguyen-th2tg Mình cũng code giống bạn nhưng khi thử bộ test 11 số [1,2,3,8,9,4,5,6,20,9,10] thì ra kết quả là 7 trong khi đáp án chính xác phải là 8 [1,2,3,4,5,6,9,10]. thật kì lạ
Dễ hiểu lắm Anh, hóng phần tiếp theo. Xem các video khác vẫn chưa thông suốt lắm.
ok cố gắng lên em :D
có add thêm cái link ở dưới description rất là hữu ích :D
Rất cảm ơn bạn nhé! Hướng dẫn của bạn có ý nghĩa với rất nhiều người. Góp ý nho nhỏ cho video sẽ tốt hơn đó là bạn hạn chế hơn việc nói đế OK vào cuối các câu nói nhé! Thói quen sẽ khó sửa nhưng làm được mà. Trân trọng!
Hay quá anh ơi, đúng cái em đang cần, ủng hộ series này 100% 😁😁
anh giảng rất hay nhưng rất tiếc em não ngắn, sau 1 hồi xem lại thì cuối cùng cũng hiểu bài dãy con tăng hđ ntn rồi:3 cảm ơn anh ạ
Riết rồi cũng hiểu cố lên em!
quá tốt luôn..cảm ơn anh đã làm em thông suốt
😆😆😆
quá hay a ơi, e thấy chuyên đề về QHD dc nhiều người săn đón ở kênh a
cảm ơn, anh dạy kỹ lắm ạ!
hay quá anh ơi, cuối cùng cũng tới phần em đau đầu nhất, ủng hộ anh
dễ hiểu, tận tình, duyệt
em ủng hộ series này ạ 😚
hay qua di em hieu quy hoach dong luon r
Cuối cùng cũng có bài toán về qhđ!
quá chất lượng, cảm ơn bạn
Hay quá anh lộc ơi. Em thích các video về qhđ lắm ạ
Ok chúc em học tốt.
Hay quá cuối cùng có series huyền thoại này :)
OK em bắt đầu thôi.
a ơi cho e hỏi là các công thức của quy hoạch động như này , a làm như nào để nghĩ ra các công thức như này vậy a ? cám ơn a nhiều
hóng mãi, quá đỉnh a ơi :33
Học anh nhiều quá em bị nhiễm chữ ok vào cuối câu nói rồi ạ huhu
Hôm trước cô gọi lên giải thích code mà em ok với cô liên tục ạ :)))
Hahaha giờ ảnh bỏ rồi em
😂
Đọc bình luận cười đau bụng luôn
chờ a mãi cuối cùng a cũng ra phần quy hoạch động
giờ lo cơm áo gạo tiền thành ra thời gian ko có rảnh như tầm năm ngoái em ạ.
@@28tech_ Video a ra chậm nhưng mà chất lượng anh ạ
vẫn ủng hộ a dài dài
Anh lên video về cách thứ hai
có độ phức tạp là O(nlogn) đi ạ
Add cho em xin link LIS độ phức tạp O(nlogn) và có in dãy với ạ. Tks add nhiều
đây dồi đây dồi =)) chúc a sức phẻ để ra nhiều phần về qhđ nữa nhen
video của anh dễ hiểu quá 😁
Thank em 🤟🤟🤟
video hay quá ạ
Cảm ơn em chúc em học tốt nhé
@@28tech_ mong anh ra nhiều video hơn nữa ạ
Ra video truy vết đi ad ơi. Cảm ơn rất nhiều ạ
3 năm trước có video này thì zui r :vv
cuối cùng cũng có quy hoạch động rồi hehe
🤟
quá hay anh ơi ~~~~
🤪🤪🤪🤪
a ơi sắp có vid về cách thứ hai có độ phức tạp O(nlogn) chưa ạ
Ok nha anh
Hồi lớp 8 cô dạy để thi hsg tin bài này mà ko hiểu chi hết, bây giờ lên lớp 10 nghe anh giảng mới thông😂😂😂, mà cho em hỏi cài đặt lis vs độ phức tạp là O(nlogn) là video nào vậy anh😢😢😢
hh trùng hợp v, hồi lp9 mình cx hc thuộc mấy bài qhd này vào phòng thi😂😂😂
Anh hướng dẫn xuất ra dãy đó luôn được không ạ
a có thể làm video hướng dẫn cách chung để giải quyết mấy bài quy hoạch động này đc k ạ
Phương pháp ấy hả hehe.
anh ơi có video lý thuyết về thuật toán quy hoạch động không ạ
em cảm ơn anh
Dễ quá bạn ei
^^
tym đầu ạ
😁😁😁
Sắp 10k rùi anh ơi🥰🥰🥰🥰
Haha, hồi em sub nó mới được có 80 90 sub.
@@28tech_ fan cứng mà anh hehe
dãy con tăng dài nhất chưa có video về truy vết và phần cải tiến ah add
Này o(n)^2 hả a có ý tưởng nào dưới nó k ạ
ra thêm các bài tập CTDL stack queue đi anh
Thế thì vô vàn lắm hehe.
làm thế nào để in ra tất cả các dãy con không giảm vậy anh
làm sao để in ra dãy đó ạ
Đi thi xài auto, themis có chấm không anh.
Anh nói to hơn ạ, em mong anh
thuật toán này là sliding window đúng không nhỉ?
Ko phải
Anh có vid cải tiến thuật toán chưa ạ
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
mấy cái dòng này là cái dòng gì vậy anh, em thấy ngta lập trình hay gắn như này nên em cx bắt chước theo chứ không thực sự biết tác dụng của nó là gì. Mong anh giải thích vs ạ, vs lại em không biết run code kiểu s khi có mấy dòng này nữa
ios_base::sync_with_stdio(false);
Dùng cin/cout bình thường sẽ bất lợi về thời gian do phải đồng bộ với stdin/stdout (vì lí do lịch sử nên phải có đồng bộ này). Gặp bài I/O nhiều phải có câu này, nếu I/O ít thì không đáng kể.
cin.tie(0); để ngăn sự đồng bộ giữa cin và cout: chỉ khi cout xuất ra hết thì cin mới nhập vào (và ngược lại). Việc đồng bộ này chỉ có chương trình tương tác mới cần.
sắp có bài lis nlogn chưa a
Chưa có em ạ
cho e hỏi trong CP thì nên xài mảng bình thường hay vector vậy a?
Em dùng cái nào cũng được, như nhau cả mà
bài này dùng lower_bound nhanh hơn anh ạ
Anh ơi cho em xin cái bài mà anh làm trong video ấy, ở hackkerrank hay sao ấy ạ
Này Ko còn rồi bạn ạ
@@28tech_ Dạ vâng ạ
@@28tech_ Vậy còn mấy bài nào liên quan cũng trên hackerrank ko ạ?
Nếu họ ko ra đề là 'dãy con liên tiếp ' thì mình tìm các phần tử cách nhau đúng ko ạ ?
Nếu mà làm dãy con giảm thì sao vậy ad
a ơi, cải tiến thuật toán đc ko a :))
Làm sao để nó hiện tiếng Việt như thế kia vậy anh ơi?
có link nộp bài k ạ
anh ơi ra vid in dãy ra chưa ạ
anh cho em xin link bài này trên hackerrank đc ko ạ
làm sao để in cả dãy ra vậy anh
ko có phần truy vết à anh
với n = 10^5 thì có thuật toán nào tối ưu k ạ
Có em nhé có thể kết hợp binary search, đợi video sau nhé
anh sử dụng phần mềm code gì vậy ạ
Sublime text nhé em
@@28tech_ dạ anh
anh làm phần truy vết đi ạ
Mình chx hiểu tại sao L[i]=max(L[i],L[j]+1), ai đó vô thông não cái
có phần giải bài này cho java không ạ
Jca em code tương tự thôi
anh ơi có phần giảm độ phức tạp của bài này chưa ạ
chưa có em ơi.
chặt nhị phân
thay vì cho L[i] = max(L[i], L[j] + 1) thì sao mình không cho L[i]++ luôn nhỉ? cũng là xét a[i] > a[j] mà
int main() {
int n; cin >> n;
vector arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
vector L(n,1);
int max_val = 0;
for (int i = 1; i arr[j]) L[i] ++;
}
max_val = max(max_val, L[i]);
}
cout
ChatGPT:
The line L[i] = max(L[i], L[j] + 1) is used to update the length of the longest increasing subsequence that ends at index i. The reason for using max(L[i], L[j] + 1) instead of just L[j] + 1 is that there may be multiple increasing subsequences that could potentially end at index i, and we want to choose the one that results in the longest overall subsequence.
Consider the following input array:
Copy code
3 4 1 5 2
Initially, the array L is set to all ones:
Copy code
1 1 1 1 1
When we process arr[2] (which is 1), we compare it to all previous elements in the array to see if it could be part of a longer increasing subsequence. In this case, it cannot be part of any increasing subsequence longer than 1, because it is smaller than all previous elements. So L[2] remains at 1.
When we process arr[3] (which is 5), we compare it to all previous elements in the array to see if it could be part of a longer increasing subsequence. It is larger than arr[0], arr[1], and arr[2], so it can be part of a longer increasing subsequence. In this case, the longest increasing subsequence that ends at index 3 is {3, 4, 5}. To update L[3], we add 1 to the length of the longest increasing subsequence that ends at j=1 (which is {3, 4}), since arr[3] is larger than arr[1]. We get L[3] = L[1] + 1 = 2.
When we process arr[4] (which is 2), we compare it to all previous elements in the array to see if it could be part of a longer increasing subsequence. It is smaller than arr[0], arr[1], arr[2], and arr[3], so it cannot be part of any increasing subsequence longer than 1. So L[4] remains at 1.
The resulting L array is:
Copy code
1 1 1 2 1
The length of the longest increasing subsequence is 2, which is correctly found by the algorithm.
If we had used L[i] = L[j] + 1 instead of L[i] = max(L[i], L[j] + 1), we would have missed the longer subsequence {3, 4, 5} and incorrectly calculated the LIS to be 1.
@@IamNix tóm lại giải thích bằng tiếng việt đi
@@luukhai3886 là bạn hiểu sai vấn đề. Nếu làm như vậy. Bạn luôn giả định phần tử áp chót luôn được chọn.
viết code mà không chuyển unikey là sao??
@@NMnhSon nó là quyền của mình, bạn có quyền gì bảo mình phỉ chuyển hay ko?
trời ơi, cứ ô kê, ô kê, khó học quá
Oke em có thể sang kênh khác học nha
@@28tech_ Vầng anh
Xin lỗi anh, em không có ý chê bài giảng cảu anh, vì em mới đang tập tành, đó có thể là do vấn đề tâm lý của em, việc lặp từ quá gây rối loạn tiếp thu, nhưng nó cũng là một vấn đề của anh
khó hiểu quá
:)))
Lsao để in dãy con đó ra v ạ