I will explain DP, one of the most important techniques in competitive programming (CP).
The goal is to solve the knapsack problem.
No prior knowledge or programming experience is required.
I've thrown exhaustiveness and precision in the trash.
Recommended DP problems: atcoder.jp/contests/dp
(26 problems, the 4th one atcoder.jp/contests/dp/tasks/... being the knapsack problem featured in this video)
Scheduled next: What is binary search? (Tentative - Coming soon)
Previous: • DFS・BFSとは?お気持ち編[競技プログラ...
Playlist: • 競プロ初心者へ / For CP Begin...
0:00 The Thief and the Treasure Vault (Knapsack Problem)
0:44 Solution by Brute-force Search
1:20 Coin Picking
3:03 DAG
3:23 Coin Picking with Bombs
4:34 DP Solution to the Knapsack Problem
X (Formerly Twitter): / evima0
Негізгі бет Ғылым және технология What's DP (Dynamic Programming)? [For CP Beginners] (English subtitles)
Пікірлер: 32