Tóm tắt 4 bước để giải 1 bài Dynamic Programming (Quy hoạch động): 1. Giải theo hướng đệ quy: Đây sẽ là cách dễ nhất để bắt đầu một bài DP. Ở bước này thì bạn không cần quan tâm đến độ phức tạp. Chỉ cần trả đúng giá trị là okay rồi. Thường thì độ phức tạp của bước 1 sẽ là khoảng O(2^N) hoặc O(N!)
2. Top-down DP: Vì khi sử dụng đệ quy, sẽ có nhiều hàm bị gọi đi gọi lại nhiều lần, chúng ta có thể cải thiện bằng cách sử dụng thêm bộ nhớ để lữu giữ giá trị trả về của các hàm đã tính. Như thế, ở những lần gọi tiếp theo, chúng ta sẽ sử dụng giá trị trong bộ nhớ thay vì tính lại từ đầu mất thời gian. Đa số mọi người sẽ dừng ở bước này. Do là độ phức tạp thời gian đã tối ưu rồi. Các bước sau mục đích là chỉ để cải thiện độ phức tạp không gian thôi.
3. Bottom-up DP: Thay vì dùng đệ quy, chúng ta sử dụng mảng để chứa các giá trị và thực hiện tính toán ngay trên mảng đó. Bước 2 và 3 sẽ có chung độ phức tạp. Tuy nhiên, đây là một bước vô cùng quan trọng để có thể tiến tới bước 4 một cách dễ dàng hơn. 4. Cải thiện độ phức tạp không gian: Dựa vào cái mảng từ bước 3, chúng ta có thể phát hiện được những giá trị mà chỉ được sử dụng cho 1-2 lần tính toán. Đối với những giá trị này, chúng ta không cần đến mảng để chứa nó làm gì. Thay vì thế, bạn hoàn toàn có thể sử dụng ít biến hơn cho việc tính toán, và chúng ta chỉ cần ghi đè lên các biến này khi nó không cần thiết nữa.
Không có câu hỏi gì là ngu ngốc. Các bạn có câu hỏi gì thì cứ thoải mái comment, mình sẽ giải đáp hết tất cả thắc mắc cho các bạn dù nó đơn giản đến đâu đi nữa.
@@CongNguyen-fi5cd trên thực tế thì quy hoạch động chỉ dùng để optimize cho app thôi em. Trừ khi app của em yêu cầu performance tối ưu từ ban đầu, chỉ cần app chạy là được. Đến lúc cần optimize thì ta optimize nó. Quy hoạch động là một trong những cách để optimize thôi em .
Các bạn có hứng thú với một topic nào đó thì cứ comment cho mình biết nhé. Dự tính của mình trong tương lai là làm về các bài cây (Binary Tree, N-array Tree).
bạn sẽ tóm tắt dynamic program i= n dãy nhà và v[i] = tiền của từng nhà và với d[n+1] = mảng để lưu giá trị cướp d[0] = 0 có nhà nào để cướp mặc định = 0 trọm sẽ bắt đầu từ nhà đầu tiên d[1] = v[1] bắt đầu từ i =2 to n+1 if(nhà hiện tại - nhà trước đó == giá trị cướp được trước đó ) then đối với nhà liền kề thì ta sẽ lấy giá trị trước i=i-1 else so sánh max(i+v[i-1],i+v[i+1]) lấy nhà hiện tại hay nhà sau kề tối ưu hơn thì i=i-1 +v[i] lấy giá trị nhà trước + với giá trị cướp được nhà hiện tại hoặc nhà tối ưu thêm vào true hoặc false để đánh dấu nhà liền kề
mình có cách tư duy ra công thức đệ quy ko ạ, thầy em dạy ko làm đc dp thì làm trâu bằng đệ quy quay lui ,còn cách từ đệ quy quay lui lên công thức dp thì thầy ko nói ạ:))
Có một số cách để làm. Ví dụ như là ở STEP 2, tại mỗi lần gọi dfs(), em có thể trả 1 tuple: (sô tiền tối đa, chain hiện tại) Lưu ý là "chain hiện tại" là một list, mục đích là sau khi so sánh dfs(i-1) và dfs(i-2), e sẽ biết là nên chọn chain nào để tiếp tục lưu giá trị hiện tại. VD: def(...): ... rv1, chain1 = dfs(i - 1) rv2, chain2 = dfs(i - 2) if ... # so sánh để tìm max và chain phù hợp return mem[i], chain + [i]
Ad ơi ví dụ có 1 cái balo chứa tối đa n kg , có một vài món vật có khối lượng A[i] và giá trị B[i] thì làm sao để balo có thể chứa đầy mà giá trị món đồ thấp nhất ạ e code sao nó ra = 0 mãi ạ
@@trunghoang-jummyegg em chat nhầm sao a gõ code linh hoạt v ạ ,khi đánh trong dấu ngoặc bay xuống hàng khác nhanh lắm luôn em thấy a không dùng vim nữa
@@trantandatvuive cũng có 1 vài lý do em ạ. Một là a cắt và chỉnh sửa video nên có thể nó trông nhanh hơn thực tế. Hai là a code nhiều và dùng vscode cũng nhiều nên quen tay.
max dfs i-1, dfs i-2 + nums[i] là sao anh em ko hiểu, là nhà cướp nhà nào ta nhà cuối cùng dfs i-1 có một mình nó à sao ko phải là dfs i-1 + dfs i-3 anh, là 2 cái nhà cách nhau cộng lại 😢
Lý do mình k có i-3 và i-4 trong công thưac này là ví i-3 i-4 sẽ tự xuất hiện khi mình đệ quy. Ví dụ Dfs(i-1) có hai option: Dfs(i-1-1) : lấy nhà trước đó mà không lấy i-1 Dfs(i-1-2) + nums[i-1]: lấy nhà i-1 và i-3
Khi chưa biết gì thì e phải xem solution trước, đến khi em có basic vững rồi thì mới không cần đọc solution trước. DP là dạng bài cực khó cần nhiều kinh nghiệm mới giải tốt được. Có công mài sắt có ngày nên kim nha em, phải rèn một thời gian dài mới giỏi được
Anh Trung Hoàng em thấy có chỗ em ko hiểu, là cái dp em hiểu r dp[-1] r compare return max cộng tiếp, còn recursion return dfs(len(nums)-1)) nó cũng tương tự như dp[-1] đúng ko anh, em thấy chưa nắm đc khúc đó ta, đó là cách mà mình return index cuối của recursion đúng ko anh, axjba 😅😆, còn cái i là cái dfs(len(nums)-1) nó đại diện cho cái dfs(i) đúng ko anh, tại sao lại là dfs(len(nums)-1) ta là cái return index cuối cùng như dp[-1] hả anh, thứ 2 là em cái approach 2 em bỏ cái return mem[i] thì nó ko work ta(line 52) á anh, em tưởng mình lưu nó vô trong cái dòng ở trên (line51) là đc r chứ ta, mong anh giải thích 2 cái thắc mắc của em, thank anh trai ❤
cái return mem[i], nếu em bỏ nó thì sẽ là return None về hàm mẹ. E cần phải xác định e muốn return gì cho đúng thì mình code như vậy. Trong trường hợp này thì mình muốn return giá trị mà mình đã lưu trong bộ nhớ trước đó. Còn phần dfs(len(nums)-1)) là dùng để kích hoạt vòng recusion đầu tiên (hàm mẹ trên cùng). Về logic thì dp[-1] là dfs(len(nums)-1)) khi mình nhìn vấn đề từ đúng hướng (top-down, hoặc bottom up). Để hiểu rõ hơn thì e thử một số example khác nhau và làm bằng tay xem (viết ra giấy)
@@trunghoang-jummyegg Anh Trung Hoàng có rảnh anh làm thêm về leetcode longest line of consecutive ones với denote the maximum bomb với number of islands, em thấy mấy cái đó cover graph với dps bfs mà em ko hiểu lắm 😂 thank anh trai ❤️
Nếu mà để ghi rõ ra từng câu chữ thì là thế này: i là vị trí nhà hiện tại. Tại nhà hiện tại mình có hai lựa chọn. Một là lấy nhà hiện tại và nhà i-2. Hai là lấy nhà trước đó (i-1) và bỏ qua nhà hiện tại. Và vì đây là đệ quy. Nên e có thể hình dung là khi mình chọn option nào đi nữa thì mình cũng tiếp tục có hai lựa chọn tại vị trí. Về cơ bản thì logic đệ quy này sẽ tiếp tục mãi mãi trừ khi e có điều kiện dừng.
![[LeetCode] Dùng Python giải Single Element in a Sorted Array | Tìm kiếm nhị phân](http://i.ytimg.com/vi/yGD3J7uz02k/mqdefault.jpg)
![[LeetCode] Dùng Python giải Single Element in a Sorted Array | Tìm kiếm nhị phân](/img/tr.png)
![[LeetCode] Giải Target Sum với Python | Quy Hoạch Động Cái Túi Phần 1](http://i.ytimg.com/vi/mNmOJ10iiLQ/mqdefault.jpg)
Cách giải thích dễ tiếp cận. Cám ơn ad nhiều , mong là có nhiều bài về đệ quy hơn.
Tóm tắt 4 bước để giải 1 bài Dynamic Programming (Quy hoạch động):
1. Giải theo hướng đệ quy:
Đây sẽ là cách dễ nhất để bắt đầu một bài DP. Ở bước này thì bạn không cần quan tâm đến độ phức tạp. Chỉ cần trả đúng giá trị là okay rồi. Thường thì độ phức tạp của bước 1 sẽ là khoảng O(2^N) hoặc O(N!)
2. Top-down DP:
Vì khi sử dụng đệ quy, sẽ có nhiều hàm bị gọi đi gọi lại nhiều lần, chúng ta có thể cải thiện bằng cách sử dụng thêm bộ nhớ để lữu giữ giá trị trả về của các hàm đã tính. Như thế, ở những lần gọi tiếp theo, chúng ta sẽ sử dụng giá trị trong bộ nhớ thay vì tính lại từ đầu mất thời gian. Đa số mọi người sẽ dừng ở bước này. Do là độ phức tạp thời gian đã tối ưu rồi. Các bước sau mục đích là chỉ để cải thiện độ phức tạp không gian thôi.
3. Bottom-up DP:
Thay vì dùng đệ quy, chúng ta sử dụng mảng để chứa các giá trị và thực hiện tính toán ngay trên mảng đó. Bước 2 và 3 sẽ có chung độ phức tạp. Tuy nhiên, đây là một bước vô cùng quan trọng để có thể tiến tới bước 4 một cách dễ dàng hơn.
4. Cải thiện độ phức tạp không gian:
Dựa vào cái mảng từ bước 3, chúng ta có thể phát hiện được những giá trị mà chỉ được sử dụng cho 1-2 lần tính toán. Đối với những giá trị này, chúng ta không cần đến mảng để chứa nó làm gì. Thay vì thế, bạn hoàn toàn có thể sử dụng ít biến hơn cho việc tính toán, và chúng ta chỉ cần ghi đè lên các biến này khi nó không cần thiết nữa.
Quá tuyệt vời ạ, cảm ơn anh đã giảng chi tiết, từng bước phối hợp giọng nói rõ ràng cực hay nữa ạ
@@ttth4974 cảm ơn em ☺️
Không có câu hỏi gì là ngu ngốc. Các bạn có câu hỏi gì thì cứ thoải mái comment, mình sẽ giải đáp hết tất cả thắc mắc cho các bạn dù nó đơn giản đến đâu đi nữa.
trog thực tế có bài làm quy hoạch không anh ,và làm sao nhận biết được bài ý là bài quy hoạch động ạ
@@CongNguyen-fi5cd trên thực tế. Ít khi em gặp những bài toán kiểu này lắm. Tuy nhiên, đi phỏng vấn, nhiều công ty vẫn sẽ hỏi
@@CongNguyen-fi5cd trên thực tế thì quy hoạch động chỉ dùng để optimize cho app thôi em.
Trừ khi app của em yêu cầu performance tối ưu từ ban đầu, chỉ cần app chạy là được.
Đến lúc cần optimize thì ta optimize nó. Quy hoạch động là một trong những cách để optimize thôi em .
Có khi bạn cũng không biết video này giúp mình nhiều như thế nào trong con đường trở thành lập trình viên đâu. Cám ơn bạn rất rất nhiều!
Cảm ơn Tuan Anh nhiều nhé 🥰!
Các bạn có hứng thú với một topic nào đó thì cứ comment cho mình biết nhé. Dự tính của mình trong tương lai là làm về các bài cây (Binary Tree, N-array Tree).
Hữu ích, dễ hiểu cho các bạn thi HSG như em ạ:)) Tks
Yay:D
Đỉnh luôn anh ơi. Xem một video mà thành fan luôn. Rất dễ hiểu 🥰🥰
Đừng quên cho mình biết nếu như video đã giúp bạn hiểu hơn về DP nhé. Hoặc nếu có gì chưa tốt trong video thì mình cũng xin nhận mọi ý kiến đóng góp.
Phạm Đoàn Tiến cảm ơn em nhiều nha!
Video rất dễ hiểu, cám ơn bạn nhiều.
sau 1 video hiểu luôn, cảm ơn a
Em cảm ơn anh vì video bổ ích này ạ
video algo hay nhất mình từng xem :D
Cảm ơn anh rất nhiều ạ.
anh giảng dễ hiểu quá 😊, thanks anh
rất hay và hữu ích ạ
Rất bổ ích, cảm ơn anh đã làm video
Dễ hiểu cực cho anh 1 like nhé
video rất hay, chi tiết và bổ ích a ơi. Cảm ơn anh nhiều ạ
Thanks em!
Chuỗi video này của anh rất bổ ích ạ ^^ hy vọng anh sẽ làm thêm, em cám ơn anh rất nhiều ạ
Okay em, anh sẽ làm thêm nhiều video nữa. Thanks em.
anh giảng rất hay❤
rất mong a ra video về leetcode graph hoặc là lí thuyết graph
bạn sẽ tóm tắt dynamic program
i= n dãy nhà
và v[i] = tiền của từng nhà
và với d[n+1] = mảng để lưu giá trị cướp
d[0] = 0 có nhà nào để cướp mặc định = 0
trọm sẽ bắt đầu từ nhà đầu tiên d[1] = v[1]
bắt đầu từ i =2 to n+1
if(nhà hiện tại - nhà trước đó == giá trị cướp được trước đó )
then
đối với nhà liền kề thì ta sẽ lấy giá trị trước i=i-1
else
so sánh max(i+v[i-1],i+v[i+1]) lấy nhà hiện tại hay nhà sau kề tối ưu hơn
thì i=i-1 +v[i] lấy giá trị nhà trước + với giá trị cướp được nhà hiện tại hoặc nhà tối ưu
thêm vào true hoặc false để đánh dấu nhà liền kề
Tuyệt vời!
cảm ơn ông nha hehe! keep it up
Thanks, Duy
video rat bo ich, em cam on anh
quá hay bạn ơi
I am your fannnnnnnnnnn !!!!!!!!
đỉnh lắm a :3
mình có cách tư duy ra công thức đệ quy ko ạ, thầy em dạy ko làm đc dp thì làm trâu bằng đệ quy quay lui ,còn cách từ đệ quy quay lui lên công thức dp thì thầy ko nói ạ:))
e muốn in ra chuỗi nhà bị cướp thì làm sao ạ
như là cái ex1 của 1, e muốn output: [1,3]
thì làm sao ạ
Có một số cách để làm.
Ví dụ như là ở STEP 2, tại mỗi lần gọi dfs(), em có thể trả 1 tuple: (sô tiền tối đa, chain hiện tại)
Lưu ý là "chain hiện tại" là một list, mục đích là sau khi so sánh dfs(i-1) và dfs(i-2), e sẽ biết là nên chọn chain nào để tiếp tục lưu giá trị hiện tại.
VD:
def(...):
...
rv1, chain1 = dfs(i - 1)
rv2, chain2 = dfs(i - 2)
if ... # so sánh để tìm max và chain phù hợp
return mem[i], chain + [i]
@@trunghoang-jummyegg dạ e cảm ơn ạ
Ad ơi ví dụ có 1 cái balo chứa tối đa n kg , có một vài món vật có khối lượng A[i] và giá trị B[i] thì làm sao để balo có thể chứa đầy mà giá trị món đồ thấp nhất ạ e code sao nó ra = 0 mãi ạ
Anh ơi a code bằng c++ đc ko ạ
cho e hỏi ạ. nếu mình tham gia các cuộc thi (hsg hay kiểu vnoi ấy) thì memory nó có ảnh hưởng chung đến total runtime không?
Cái đó a k rõ em. Nhưng a có đọc một số đề thi hsg thì người ta sẽ nêu cụ thể về limitation nếu có.
vip
sao a chỉ chuyển mouse linh hoạt hay vậy ạ
Là sao nhi?. A k hiểu ý em lắm.
@@trunghoang-jummyegg em chat nhầm sao a gõ code linh hoạt v ạ ,khi đánh trong dấu ngoặc bay xuống hàng khác nhanh lắm luôn em thấy a không dùng vim nữa
@@trantandatvuive cũng có 1 vài lý do em ạ. Một là a cắt và chỉnh sửa video nên có thể nó trông nhanh hơn thực tế. Hai là a code nhiều và dùng vscode cũng nhiều nên quen tay.
max dfs i-1, dfs i-2 + nums[i] là sao anh em ko hiểu, là nhà cướp nhà nào ta nhà cuối cùng dfs i-1 có một mình nó à sao ko phải là dfs i-1 + dfs i-3 anh, là 2 cái nhà cách nhau cộng lại 😢
Lý do mình k có i-3 và i-4 trong công thưac này là ví i-3 i-4 sẽ tự xuất hiện khi mình đệ quy. Ví dụ
Dfs(i-1) có hai option:
Dfs(i-1-1) : lấy nhà trước đó mà không lấy i-1
Dfs(i-1-2) + nums[i-1]: lấy nhà i-1 và i-3
Anh ơi để học tốt dp thì mình có nên xem solution 1 số bài trước không ạ . em mới học dp mà k nghĩ ra nổi công thức hay ý tưởng gì luôn ạ
Khi chưa biết gì thì e phải xem solution trước, đến khi em có basic vững rồi thì mới không cần đọc solution trước. DP là dạng bài cực khó cần nhiều kinh nghiệm mới giải tốt được. Có công mài sắt có ngày nên kim nha em, phải rèn một thời gian dài mới giỏi được
Anh Trung Hoàng em thấy có chỗ em ko hiểu, là cái dp em hiểu r dp[-1] r compare return max cộng tiếp, còn recursion return dfs(len(nums)-1)) nó cũng tương tự như dp[-1] đúng ko anh, em thấy chưa nắm đc khúc đó ta, đó là cách mà mình return index cuối của recursion đúng ko anh, axjba 😅😆, còn cái i là cái dfs(len(nums)-1) nó đại diện cho cái dfs(i) đúng ko anh, tại sao lại là dfs(len(nums)-1) ta là cái return index cuối cùng như dp[-1] hả anh, thứ 2 là em cái approach 2 em bỏ cái return mem[i] thì nó ko work ta(line 52) á anh, em tưởng mình lưu nó vô trong cái dòng ở trên (line51) là đc r chứ ta, mong anh giải thích 2 cái thắc mắc của em, thank anh trai ❤
cái return mem[i], nếu em bỏ nó thì sẽ là return None về hàm mẹ. E cần phải xác định e muốn return gì cho đúng thì mình code như vậy. Trong trường hợp này thì mình muốn return giá trị mà mình đã lưu trong bộ nhớ trước đó.
Còn phần dfs(len(nums)-1)) là dùng để kích hoạt vòng recusion đầu tiên (hàm mẹ trên cùng).
Về logic thì dp[-1] là dfs(len(nums)-1)) khi mình nhìn vấn đề từ đúng hướng (top-down, hoặc bottom up). Để hiểu rõ hơn thì e thử một số example khác nhau và làm bằng tay xem (viết ra giấy)
@@trunghoang-jummyegg Anh Trung Hoàng có rảnh anh làm thêm về leetcode longest line of consecutive ones với denote the maximum bomb với number of islands, em thấy mấy cái đó cover graph với dps bfs mà em ko hiểu lắm 😂 thank anh trai ❤️
@@suneosama939 a cos bài number of island nè em: th-cam.com/video/3HUVEHmM6UY/w-d-xo.html&ab_channel=TrungHo%C3%A0ng
Làm về backtracking đi a
Để a note lại r làm từ từ nhé. Thanks em !
return max(dfs(i-1), dfs(i-2) + nums[i]) anh giải thích dòng này giúp em đc ko em ko nắm đc concept ta 😢 giúp em với anh Trung Hoàng đẹp trai
Nếu mà để ghi rõ ra từng câu chữ thì là thế này:
i là vị trí nhà hiện tại. Tại nhà hiện tại mình có hai lựa chọn.
Một là lấy nhà hiện tại và nhà i-2.
Hai là lấy nhà trước đó (i-1) và bỏ qua nhà hiện tại.
Và vì đây là đệ quy. Nên e có thể hình dung là khi mình chọn option nào đi nữa thì mình cũng tiếp tục có hai lựa chọn tại vị trí. Về cơ bản thì logic đệ quy này sẽ tiếp tục mãi mãi trừ khi e có điều kiện dừng.
@@trunghoang-jummyegg à i là vị trí nhà mà cái nums[i] nó iterate, em cám ơn anh, anh Trung Hoàng đẹp trai tài năng có tâm có tầm em cám ơn anh