Re: [問題] 新手解題請教
※ 引述《kaney (蘇老師)》之銘言：
: 各位python前輩們好,第一次在python版發文
: 小弟是剛自學python不久的初學者(之前0相關基礎)
: 僅有看了coursera一個specialization 'Python for everybody'
: 跟run了一遍codecademy的learn python
: 一位朋友說可以先試著做做題目，然後推薦了我高中生程式解題系統
: 我從基礎問題做起，目前有遇到幾個困難，希望不會太打擾大家
: 題目1: https://zerojudge.tw/ShowProblem?problemid=a229
: 我的code: https://ideone.com/ehkyc7
: *腦中第一時刻浮現排列組合，上網找了下可用的方法後寫了這個
: 不過在測資不大時可以跑完，測資數值大的時候直接memory error
: 有想過從左開始一步步加括號，然後判定是否合理，
: 但是不知道要怎麼實現，例如第一畫左之後，第二畫可以加左也能加右要怎麼判斷
這題除了遞迴以外，也可以用DP的做法
觀察一下n=3的例子
用第一個括號來分組的話，可以看出來規律是這樣
裡面有兩個括號，後面沒有括號
( (()) )
( ()() )
裡面有一個括號，後面有一個括號
( () )()
裡面沒有括號，後面有兩個括號
()(())
()()()
而n=2的答案是
(())
()()
n=1的答案是
()
n=0的答案是什麼都沒有(i.e. 空字串)
所以說，如果我們已經先算出0~n-1的答案的話
那n的答案就是:
( 所有n-1的答案 ) 所有0的答案
( 所有n-2的答案 ) 所有1的答案
...
( 所有n-i-1的答案 ) 所有i的答案
...
( 所有0的答案 ) 所有n-1的答案
實作上，我們只要從小算到大，就可以保證在算n的時候0~n-1都已經算完了
results = [['']] # result of n=0
for n in range(1, 13+1): # calculate until n=13
result = []
for i in range(n):
for outside in results[i]:
for inside in results[n - i - 1]:
result.append('(' + inside + ')' + outside)
results.append(result)
print n, result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 126.74.152.122 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1572654922.A.E86.html
※ 編輯: flarehunter (126.74.152.122 日本), 11/02/2019 08:39:25
※ 編輯: flarehunter (126.74.152.122 日本), 11/02/2019 08:45:40
※ 編輯: flarehunter (126.74.152.122 日本), 11/02/2019 08:46:43
推
11/02 13:04,
4年前
, 1F
11/02 13:04, 1F
推
11/02 18:06,
4年前
, 2F
11/02 18:06, 2F
推
11/03 19:05,
4年前
, 3F
11/03 19:05, 3F
→
11/03 19:06,
4年前
, 4F
11/03 19:06, 4F
推
11/04 18:49,
4年前
, 5F
11/04 18:49, 5F
討論串 (同標題文章)