往googler的路上day3

今天學了動態規劃!!

但是找了好久的資料指大概懂了費式數列以及0/1knapsack problem。

原本預計花兩天搞懂動態規劃，但是其實還是太難了，再增加一天！

明天繼續挑戰！

演算法筆記 //之後精熟動態規劃用
http://web.ntnu.edu.tw/~algo/KnapsackProblem.html#8

台大資管-運算思維

選或不選
背包問題就是 工廠訂單問題 投資問題

背包問題的表格中可以看到
1.若沒辦法放進去，直接沿用上面表格的結果
2.若可以放進去，則比較max(放進去+上一表格剩下公斤對應value, 上個表格value)
假設剩下1公斤，直接看上個表格1公斤是多少就可以了
因為背包問題的演算法會確保同一列中，右邊的數字必定大於等於左邊的數字。
此外，我們會發現在背包問題中，下面的數字必定大於上面的數字。

因此程式碼

buttom-up
1.can often save space
2.tropological sort
3.
MIT Classes
1.DP = careful bruteforce
2.DP = subproblems + “re-use”
3.first thing is to find what is the subproblem that help solve the problem
4.don’t count recursiom
yt動態規劃 // https://www.youtube.com/watch?v=vYquumk4nWw&t=573s&ab_channel=CSDojo
1.recursion
2.recursion + memoized(邊做邊存)
3.buttom up (利用迴圈從頭開始)

動態規劃 //未完待續https://reurl.cc/KxX42R
1.確定狀態
(1)一般來說動態規劃都需要開一個數組 ex:f[i], f[i][j]
(2)最後一步
(3)子問題
2.