將整型數(shù)組分組，使兩組中各元素加起來(lái)的和相等，求分組方法有多少種。如：數(shù)組{1,1,1,1,2,2}有a組（{1,1,1,1}）、b組（{2,2}）；a組（{1,1,2}）、b組（{1,1,2}）；a組（{2,2}）、b組（{1,1,1,1}）三種分組方法。求算法思路。
2 回答
烙印99
TA貢獻(xiàn)1829條經(jīng)驗(yàn) 獲得超13個(gè)贊
我覺(jué)得是這樣，因?yàn)榉殖蓛山M且和相等，那么和一定是sum/2，這里可以有個(gè)特判是否無(wú)解。
然后問(wèn)題成了有多少組合和為sum/2的動(dòng)態(tài)規(guī)劃
dp(i,j) = dp(i-1,j-a(i))+dp(i-1,j)
解釋為前i個(gè)元素和為j的組合有多少種
答案應(yīng)該要/2
不知道對(duì)不對(duì)，感覺(jué)沒(méi)問(wèn)題，爪機(jī)碼字歡迎指教。
添加回答
舉報(bào)
0/150
提交
取消