算法分析与设计课后习题

合并数字的最大代价

$$\begin{flalign} &MAXMERGE():\\ &for\ i=1 \ to \ n-1\\ &\qquad C[i, i] = 0\\ &for\ i=1 \ to \ n\\ &\qquad for\ j=i+1 \ to \ n\\ &\qquad \qquad C[j, j+i] = -\infty \\ &\qquad \qquad for\ r=j \ to \ j+i-1\\ &\qquad \qquad \qquad t = C[j, r]+C[r+1,j+i]+\Sigma_{k=j}^{j+i}k\\ &\qquad \qquad \qquad if\ t>C[j, j+i]\\ &\qquad \qquad \qquad \quad C[j, j+i]=t \end{flalign}$$

最长增长子序列问题

$$\begin{flalign} &MaxLengthSub():\\ &n = S.length\\ &for\ i=1\ to \ n\\ &\qquad dp[i]=1\\ &for\ i=1\ to \ n\\ &\qquad pre[i]=\infty \\ &\qquad for \ k=1 \ to \ i\\ &\qquad \qquad if\ a_k<a_i\ \&\& \ dp[i]<=dp[k]+1 \\ &\qquad \qquad \qquad dp[i]=dp[k]+1\\ &\qquad \qquad \qquad pre[i]=k\\ &\qquad \qquad \qquad if\ pre[i]>k \\ &\qquad \qquad \qquad \qquad pre[i]=k \\ &maxLength = -\infty, lastIndex=0\\ &for\ i=1 \ to\ n\\ &\qquad if\ maxLength<dp[i]\\ &\qquad \qquad maxLength=dp[i], lastIndex=i\\ & k=lastIndex\\ &while\ pre[k]\\ &\qquad path.unshift(pre[a_k])\\ &Print(path) \end{flalign}$$

赏