课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

参考资料：

https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf

https://piazza.com/class_profile/get_resource/honxzoabz711ew/hvep5i3vb292gs

这次回顾HW7。

2. Copper Pipes

  • $dp[n] = \{0\}$（$dp[i]$表示长度为$i$对应的最大值）
  • for $i=1,\ldots, n$:
    • $dp[i] = p[i]$
    • for $j=1, \ldots, i - 1$:
      • $dp[i]=\max(dp[i], dp[i-j] + p[j])$
  • return $dp[n]$

3. A Dice Game

参考资料：

https://personal.vu.nl/h.c.tijms/APMNarticle.pdf

(a)

公式解释：

  • 第一部分：选择roll。
    • 情形1：当前roll到$1$，那么进入Bob的回合。
    • 情形2：当前rool到$2\le i \le 6$，那么依然为Alice的回合。
  • 第二部分：选择pass，此时进入Bob的回合，当前running total为$0$。

补充：

满足如下条件时，

我们有

另一方面，如果

我们有

(b)

  • 显然$x,y,z$的范围都在$0$到$N$之间。

  • 对于$x + z \ge N, y < N$，初始化$W(x,y,z) = 1$

  • 对于$y=N$，初始化$W(x,y,z)= 0$

  • for $x=N-1,\ldots, 0$

    • for $z = N-1,\ldots, 0$

      • for $y = N - 1,\ldots, 0$

4. Road Trip

  • 构造数组$dp[n + 1][C+1]=\{\infty \}$，其中$dp[i][j]$表示到达第$i$个站点，剩余$j$加仑汽油的最少开销。
  • 初始化$dp[1][j] = c_1 \times j$
  • for $i=2,\ldots, n$:
    • for $j = 0,\ldots, C$:
      • for $k = 0,\ldots, j$:
        • $k$表示在第$i$站加了$k$加仑汽油。
        • $dp[i][j] =\min(dp[i][j], k\times c_i + dp[i - 1][j-k+ (d_{i}-d_{i-1})/m] ) $
  • return $\min_{j=0}^{C} dp[n][j]$

时间复杂度：

5. Non-PrefixCode

  • 构造数组$dp[n+1]=\{0 \}$，其中$dp[i]$表示匹配前$i$个比特串的数量。
  • for $i=1,\ldots, n$:
    • for $j$ in $d$:
      • $c= d[j], l = \text{len}(c)$
      • if $s[i-l+1:i] =c$:
        • $dp[i] += dp[i - l ]$
  • return $dp[n]$

时间复杂度：

两重循环时间复杂度共$O(nm)$，字符串匹配时间复杂度为$O(l)$，所以总时间复杂度为$O(nml)$。

6. A HeLPful Introduction

(a)

注意到$(0,0)$满足所有限制，所以不存在$a,b$，使得区域不可行。

(b)

如果$b=0$，那么约束为

显然$x+y$可以趋向于正无穷。

如果$b>0$，那么约束为

当$a \le 0$时，约束区域无边界，从而$x+y$没有上界。

当$a> 0$时，约束区域有边界，从而$x+y$有上界。

如果$b<0$，那么约束为

此时约束区域无边界，从而$x+y$没有上界。

从而无上界的条件为

  • $b\le 0$或$b>0,a\le 0$
(c)

有上界的条件为

  • $b>0, a>0$

如果$a\neq b$，那么$x+y$的最大值有唯一可行解。

7. Spaceship

假设部件$1,2,3$的数量分别为$x,y,z$，那么我们的目标是最小化

这等价于最小化

约束条件为