What's DP (Dynamic Programming)? [For CP Beginners] (English subtitles)
Вставка
- Опубліковано 20 лип 2024
- 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 DFS & BFS? [For CP Beginners] (English subtitles)](http://i.ytimg.com/vi/0_9heBS7Flg/mqdefault.jpg)
![What's DFS & BFS? [For CP Beginners] (English subtitles)](/img/tr.png)
![Which is Bigger: Fukasetsu Fukasetsuten or Graham's Number? [English Subtitles]](http://i.ytimg.com/vi/3wurgrmYGiw/mqdefault.jpg)
解り易さの極みですやん
The best video to introduce DP I've ever seen.
とある共テ模試の情報でこれ出たの鬼畜
単位重さあたりの価値の大きい順にして解いたけど、動画の解法の方がほかの問題に応用できていいですね...
勉強させていただきます✍
単位重さあたりの価値が大きい順に足しても正しい答えにならないケースがあります。
@@snorlaxNK
上限10kg
宝物1：1gで1円
宝物2：10kgで1000円
みたいな場合とか？
正しい答えにならないケースがまあまああるけど、どのみちナップザック問題はNP-Hardだからヒューリスティックな解法の初期値としてとか、いっそのこと不正確なことを承知で見積もるために使うとかの使用法ならアリかも
お気軽に質問してください。（動画とそこまで関係なくても構いません。）
Feel free to ask questions. (Even if they are not very relevant to the video.)
わかりやしー
will you show more videos of algorithm introduction like this in the future？it really improves my programming idea quickly. and thank you very much！
I second that ! maybe you can create a series of programming tutorials covering all algorithms that is being used in programming contests...that will really help us ...Thanks Evima, keep doing what you are doing
図の読み取り方はギリギリわかったのですが、図の作り方がわからなかったです。。。
勉強します！！
すみません、今回は理論のみで一つの話として完結してしまったので、純粋な「お気持ち編」としてコードでの実装は省いてしまいました。
より実践的な動画を来月作るつもりです。おそらく「DP まとめコンテスト」（atcoder.jp/contests/dp ）の解説という形にします。
なお、このコンテストの4問目（atcoder.jp/contests/dp/tasks/dp_d ）が動画で扱ったナップサック問題です。
ありがとうございます！
もっと初歩段階でつまづいてまして、、最初の宝石泥棒のナップサック問題を全探索しないで解く為に動的計画法を使ったと思うのですが、、
その際の有向非巡回グラフの作図の仕方がわからなかったです。。
@onotomi6328
4:56 宝石を好きな順に一列に並べてから、(左から)○番目までの宝石まででぴったり△kgにしたいときの最大金額、を考えてます
例えば 1円10kg, 2円10kg, 4円20kg の3宝石が並んでいて、ぴったり20kgぶん選ぶなら、1円+2円の組より4円20kg単品のほうがベスト(だから1+2円で20kgにする方法は今後考えない)みたいな感じです
5:06 ○番目の宝石を拾うなら、その重さぶん斜め下方向に移動するグラフです
合計4kg以上になる場合は考えないルールにしています
@@JD-is8yg
ありがとうございます！
好きな順と全探索のときにやった2通りをそのまま道に図示すれば良いのもわかりました！
コメント読んでちゃんと動画みたらちゃんと理解できました！
5:16 why there's no transition shown from 0,0 to 1,1 (with 20Y), and 1,2 (with 30Y) ??
oh wait, the DAG given below follows the FA shown above. ohwkay.
Feel free to ask questions. (Even if they are not very relevant to the video.)
I'm confused and distracted by many sheets and roadmaps, if I participate in atcoder-codeforces contests and do upsolve and learn new algorithms in the way , is it a good way to practice and train or I should follow a roadmap or practice on a specific rate and up
I would say you can ignore those "roadmaps."
The people who made those things most likely have different backgrounds from yours, so they probably don't work too good. If a particular roadmap is working for you, then you can focus on that one thing, but otherwise you can safely forget them. I think in many cases it's best to just participate in contests and learn new techniques "in the way."
@@evimalab contests are for improving speed of what you already know. for getting to know concepts in first place, sort the archive of problems in increasing difficulty order, then solve them one by one.
> _"I think in many cases it's best to just participate in contests and learn new techniques "in the way.""_
DP first or graph to learn
Hi, I have been following your playlist. It would be good if u add some practice problem related to the video topic.
problems can be from atcoder or anywhere.
I mean standard / must do problem on that topic
Thanks! Well, for DP I'd recommend Educational DP Contest on AtCoder (atcoder.jp/contests/dp ), which has 26 fairly standard DP problems, the 4th one being the knapsack problem featured in this video. I'll add this to Description. (Actually, I'm planning to make a video that explains this whole contest, maybe next month?)
Codeforces's problem tags and difficulty sorting may also be useful (codeforces.com/problemset?order=BY_RATING_ASC&tags=dp ), but it may be tricky to find easy problems that actually require DP. (Maybe avoid ones that also have "greedy"?)
By "very overview", perhaps you meant "brief overview"?
I tried to reflect part of the Japanese title "お気持ち編" (literally "Emotional Edition") which meant that the video is not a formal introduction to DP, and it seems I did it wrong. Thanks for letting me know, I'll replace it with something else.
"non-technical overview" or just "brief overview" would work, I get what you're trying to say here. @@evimalab
To be honest, though, it's probably not required and may be omitted. (Maybe you need a translator for you? But I don't understand Japanese.)
Thanks for the suggestions! Now that I think about it, it's probably best to just omit it since the title was already quite long. Now the title reads "What's DP (Dynamic Programming)? [For CP Beginners] (English subtitles)," which still uses 71/100 characters.
Ironically, I'm a (technical) translator at AtCoder without experience of real-life English. When this channel grows, I might eventually need a translator, but I have long, long way to go before that really makes sense :)
If you have time, could you tell me what was weak about my writing in my first response (the one beginning with "I tried to reflect")? GPT-4 said there was no clear error.