想請教其中的兩題
第一個是第5-a的第3題
https://i.imgur.com/tNV1Egl.jpg
寫的時候並不知道in place的意思
寫完之後上網看了一下維基百科
上面寫說quick-sort常被描述為inplace演算法，但實際操作的時候需要一個O(logn)的sp
ace來支援quicksort中的遞迴
所以這題到底要寫T還是[email protected]@
然後是最後一題的DP
https://i.imgur.com/erjeBip.jpg
想問一下有比較快速的計算方式嗎還是真的得每一次每一次下去算..
到長度6或7以上的時候其實蠻多種組合要去試的
還是沒有就只能慢慢算？

遞迴的空間不算

Qsort寫exchange 所以沒有用到額外空間 是inplacedp列出定義還有recurrence 剩下就只能乖乖算總共10項 從左填到右 每次最多3個規則 應該不會太久(?這樣你沒辦法說明第2題

最後一題那個我記得計算量算少的吧（？你是不是用純暴力法沒用DP舉個例長度7的時候末端只有#2 #7可以 所以你就算 長度五+#2 長度四+#7 選小的就是了

不能這樣算 也有可能長度9+三角形所以還是要從左邊一格一格填如果題目設計好一點的話 沒有greedy choice property按照樓主的算法應該會算錯

對啦還有 長度六+三角形 這樣就好了啊

最後一題不用想太複雜吧 觀察可以得到每種轉換最多只能讓一個圖案減少1的cost(如#1,4,5,7) 所以就從最前面的圖案開始找看看能不能用#1,4,5,7去轉換 找得到就繼續往下找直到所以圖案都用#1,4,5,7轉換過

alex那個是正解