Re: [理工] [資結]-中央98-資工所
※ 引述《luckyburgess (心安即自在)》之銘言：
: 想問第5題的解答
: http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_98_01.pdf
: 麻煩幫我解答一下 !!感謝囉!
標準的DP題目
(1)
A[i]=x0+x1+...+xi, 即A[i]為x0到xi的總和
由此不難推知以下的遞迴式:
if i =0, A[i]= x[0];
if i!=0, A[i]= A[i-1]+ x[i];
用for loop即可在O(n)得出上述A陣列
A[0]=x[0];
for(i=1 ; i< n ;++i){ //n 為A陣列大小
A[i]=A[i-1]+x[i];
}
(2)
d[i,j]=x_{i}+x_{i+1}+x_{i+2}+...+x{j}
=x_{0}+x_{1}+...+x{j} - ( x_{0}+x_{1}+...+x_{i-1} )
=A[j]-A[i-1]
以上用for loop可在O(n^2)內解決
for(i=0 ; i<n; ++i){
for(int j=i; j<n ;++j){
if(i==0){
d[i][j]=A[j];
}
else{
d[i][j]=A[j]-A[i-1];
}
}
}
綜合(1)(2), 整體複雜度O(n^2), 為其所求。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.107.174.109
推
03/19 23:44, , 1F
03/19 23:44, 1F
→
03/20 00:13, , 2F
03/20 00:13, 2F
推
03/20 00:31, , 3F
03/20 00:31, 3F
※ 編輯: privatewind 來自: 120.107.174.109 (03/20 00:50)
→
03/20 00:50, , 4F
03/20 00:50, 4F
推
03/20 09:17, , 5F
03/20 09:17, 5F
→
03/20 09:17, , 6F
03/20 09:17, 6F
推
03/20 09:25, , 7F
03/20 09:25, 7F
討論串 (同標題文章)