想請問大家在算OBST時
Cost矩陣的對角線是放0還是外部成本呢？
一直以來我在算的時候都放外部成本，但我昨天發現資結的算法在計算Cost的時候對角線
都是放0，這樣答案會有全部外部成本的差距。
資結跟演算法的定義是不是常常有小出入呢

要注意他們的I,j從哪裡開始你把例子貼上來 大家會比較好跟你解釋

外部成本聽起來很像社會科學那個xD 要看題目怎麼定義

https://i.imgur.com/46YJjCV.jpghttps://i.imgur.com/heyhAeJ.jpg這題如果放外部成本cost是2.4如果放0就會如答案所說是2.0

這是DS跟ALGO對外部節點定義不同的關係考試的時候 你就把假設寫清楚應該就好了

我覺得這東西用陳立宇交的方式去算比較簡潔(就三個倒三角形的表格然後差別只是失敗的成本定義dp問題只要搞懂遞迴的由來跟表格大概的長相，ds跟algo這里的差別也只是遞迴差一點點，反正先列出遞迴在作答比較好是林立宇幹我打錯XD而且表格是正三角形的XD

我好像只會洪逸的算法欸==一直覺得演算法那個很不直觀，這樣ok嗎？

好吧 其實沒關係啦 搞清楚為什麼algo跟ds有什麼差就好然後用你喜歡的算法就好了

我也是用林立宇的方法算xd，覺得視覺上比較好記憶

原本也是用洪逸的算法，直到遇到10個點的BST.....

那可不可以教一下怎麼林立宇算法？哈哈哈以為業配

林立宇算法好像就是楓葉本算法去找原文書xddobst超煩的，有夠難算，但是又會考全套= =

其實算法沒什麼差 只是他的那個表格我覺得很乾淨他只是把表格化成三個cost/weight/root然後他定義的cost(i,j)那個ij我覺得比較直覺我記得洪逸的定義cost(i,j)好像是不包含i還是j的OBST我看過的DP的運算 算起來都有一個規律其實就算七八個點的obst 算起來大概也是十分鐘以內就可以完成https://i.imgur.com/zp6JiZy.jpg我也是先看洪逸的那個表格看到覺得很痛苦這個舒服多XD

樓上在洗三溫暖 （別理我是說~T大你的算法好像就是algo算法 只是擺橫的 無意冒犯

是啊，林立宇算法就是algo算法

我覺得這一橫擺算起來的感受就有差啦XD

我覺得DS跟演算法有重疊的部分還是以演算法為主 DS原文聖經那本本來就很…

我也不太喜歡Horowitz那本

我剛剛想說很久沒算obst算一下成大那題 11分鐘 真他媽垃圾題目我是看algo之後才看出這個dp算式的規律是啥的

怎麼嚕？不就用演算法寫而已嗎？

沒啊成大去年考一個七個點的真的算到很煩XD

n^3 手算很想死啊

沒事沒事 分數拿到 就一生平安！