Peienwu's Blog

這兩週真是風風雨雨，首先第一週是段考週，所以有很多時間拿去惡補段考。第二週則是疫情關係要在家裡線上上課，結果進度就辣了一大截…趕快追QQ！

上課內容

一堆的背包問題（真的很多種耶）

01背包問題
無限背包問題

• 先固定背包數量看價值跟先固定價值看背包數量可以互換

  閱讀全文 »

上課內容

• 使用DP時機：

  • 最優解問題
  • 計數問題
  • 重複子問題

• DP 使用過程

  • 定義狀態
  • 狀態轉移
  • 找到一個會AC的作法，再慢慢優化

上課內容

分治法，一開始講了三個證明遞迴複雜度的方法：

1. 取代法：
   三步驟：Guess, Verify, Solve
   靠經驗假設，並驗證（加一些常數之類的）
2. 遞迴樹法
   不太嚴謹，提供猜答案想法，最後用取代法驗證
   畫出遞迴樹
3. 主定理（Master Theorem）
   比較f(n) 和 n^(logba)的關係
   大於等於小於有三個複雜度
   閱讀全文 »

這一週主題是Greedy，其實貪心法的題目要難可以到很難，有點像一個抽象的想法，需要透過反覆的實作與練習（顯然我缺乏），來更容易的想到題目的解法！

上課內容

影片的內容主要是在證明greedy 的正確性，超複雜的數學證明（又是數學證明！）
原本以為上課會延續證明的內容，沒想到完全沒有講到證明的內容，都是在講解例題（也不錯，有很多題需要慢慢理解）
所以列了上課講過的例題，一定要搞懂！

上課內容

這一週的主題是枚舉(enumeration)，內容主要環繞二分搜、三分搜、DFS剪枝這些部分。
這一週的內容算是相對輕鬆，解數獨的部分也是蠻有趣的！

前兩次上課還沒來得及補齊，先來紀錄一下第三週的內容

上課內容

這一週的主題是基礎圖論、淹水問題(BFS)還有Heap!把這幾個單元排在一起真的是負擔很重QQ

第一次上課，原本想說會輕鬆的度過一個禮拜
沒想到直接用單調隊列當作開場，讓第一個星期圍繞著stack 與queue的資結世界中
但也很慶幸的，在第一週終於學會用很節簡的程式碼寫單調隊列
第二週的內容則是複雜度分析
P 與NP 問題真讓人一頭是大，雖然在競程中對於較複雜的複雜度問題很少派上用場
不過還是蠻有趣的，只要證明P=NP就可以很多錢了！

資訊之芽的上課內容，用了幾節下課加回家的時間把程式實作出來
用紙跟筆解數獨的過程就是把所有可能剔除明顯不可能的之後下去試，如果遇到問題就換下一種方式

tioj-1354 池塘裡的青蛙

題序
這是一個排列組合的數學題目，透過動態規劃紀錄小問題的答案

動態規劃的要素

可以動態規劃的問題符合兩個條件

• 重複子問題
• 可分治性

動態規劃的三要素

• 0.定義
• 1.狀態轉移方式
• 2.初始狀態（邊界條件）