CSCI3160 Special 6：递推求值、完整表格与切割费用

原件：Sp06 题目（本地课件） p.1；Q3另核对L08（本地课件） p.4。 每题先题解后解析；Q2存在边界遗漏，题解明确区分原式与修正约定。

Problem 1：线性时间求 Fibonacci

题解

n=0返回0；否则保存a=0、b=1，从t=2到n反复同时更新(a,b)=(b,a+b)，最后返回b。时间O(n)，额外空间O(1)。

具体解析

处理t之前，a=f(t−2)、b=f(t−1)，因此新b恰为f(t)，新a恰为f(t−1)，循环不变量成立。必须同时更新或用临时变量，先改a再用新a算b会重复使用错误值。自取n=6，数列为0、1、1、2、3、5、8，结果8。

题目明确每个数能装进一个word，所以加法为常数；不允许据此推广到无界n的大整数位复杂度。递归重复展开会反复计算相同f值，顺序DP则每项一次。

Problem 2：区间递推缺失相邻边界

题解

原式i=j时为0，i<j时取内部k=i+1,…,j−1的最小值再加A[i]A[j]。当j=i+1，内部集合为空，原题不能唯一确定有限数值。若补给相邻值B[i]，则按j−i递增填表，枚举所有内部k，O(n³)时间、O(n²)空间。

具体解析

PDF渲染已确认上界j−1、下界i+1，不是文字提取漏掉端点。不能擅自把内部范围改成允许k=i或k=j，那会让f依赖自身；也不能把空min偷偷当0。

f[i,i] ← 0；f[i,i+1] ← B[i]
对gap=2,…,n-1：
    对i=1,…,n-gap：
        j ← i+gap
        f[i,j] ← A[i]A[j] + min(f[i,k]+f[k,j]，i<k<j)

依赖跨度严格更短，因此计算次序有效。状态O(n²)，每状态O(n)候选，总O(n³)。若自行约定B[i]=0、A=[2,3,4]，则f(1,3)=8；若B为10、20，值为38，说明原定义的遗漏确实影响结果。采用扩展实数min空集=∞则所有非单点状态为∞，虽形式可算，却不能当作原题明确给出的有限语义。

Problem 3：ABC与BDCA的全部f表

题解

完整结果如下；行表示x的前i字符，列表示y的前j字符。

具体解析

首行首列与空串比较，值0。A这一行只有遇到列A时相等，取左上0+1；B这一行遇到第一列B得1，此后字符不等，沿上、左最大保留1；C在第三列匹配，取f(2,2)+1=2，最后一格字符C与A不同，取max(f(2,4),f(3,3))=2。

表中f(1,4)=1但f(3,4)=2不代表连续共同子串；这是LCS长度，可以跳过字符。对应最终公共子序列为BC，y中跳过D，长度2。

Problem 4：长度5钢条的最大收入

题解

最大收入14，可切成2+2+1，卖价6+6+2=14。

具体解析

价格为P=[2,6,7,9,10]。逐长枚举第一段得到：

每个合法切法都有一个第一段i，剩余长度t−i最优收入由已算表给出，因此枚举没有漏方案。整根卖只得10，不能由价格随长度上升就认为不切最好。

Problem 5：每次切割收固定费用

题解

设R[0]=0，对t≥1：

按t递增求值并记最佳i；i=t表示整根不切。总时间O(n²)、空间O(n)，恢复至多O(n)。

具体解析

整根出售不发生切割，不能减c；若i<t，先切下长度i需一次费用c，剩余部分内部所需费用已经包含在R[t−i]中，不重复计。含q段的最终方案共做q−1次切割，这个递归恰好每个非最后段扣一次。

沿用Q4价格，自取c=2：R[1..5]=[2,6,7,10,11]。长度5取第一段2，再把剩下3整段出售，价值6+7−2=11；切成2+2+1则14−2×2=10，整根10。可见原来最优的多段切法加入费用后可能不再最优。t=1内部候选为空时，保留不切候选P[1]即可，不存在Q2那样无基例的问题。

逐候选核对最后一格，避免每段都误扣费用。 Q5 中 $c=2$，前面已得 $R_1=2,R_2=6,R_3=7,R_4=10$。长 5 的所有首段选择为：

选首段 2 后余段 3 不再切，得到 2+3，两段只有一次实际切割，净值 $6+7-2=11$。若分为 2+2+1，三段需要两刀，净值 $6+6+2-2\cdot2=10$。递推减去的是当前新的一刀，子问题收入已经扣过内部刀数；不要再次给子问题每一段重复收费。

来源与证据

Sp06 p.1、L08 p.4；数值表已独立计算。Q2保留未定义边界说明，未编造官方条件。