https://cs170.org/

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

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

1. Shortest Paths with Dynamic Programming!

(c)

dependency graph是有向无环图。

(f)
• $d(S,C)=2$
• $d(S, A) = 1$
• $d(S,B)=7$
• $d(S,D)=5$
• $d(S,E)=6$

2. String Shuffling

2

• 定义数组$dp[|x| + 1][|y| + 1] = \{0\}$
• $dp[0][0] = 1$
• for $i=1,\ldots , |x|$:
• $dp[i][0] = dp[i - 1][0] \land (x[i] == z[i])$
• for $j= 1, \ldots, |y|$:
• $dp[0][j] = dp[0][j - 1] \land (y[j] == z[j])$
• for $i=1,\ldots , |x|$:
• for $j= 1, \ldots, |y|$:
• $dp[i][j] = (dp[i-1][j] \land (x[i] == z[i + j])) \lor (dp[i][j-1] \land (y[j] == z[i + j]))$

• 定义数组$dp[|y|] = \{0\}$
• $dp[0] = 1$
• for $j= 1, \ldots, |y|$:
• $dp[j] = dp[j - 1] \land (y[j] == z[j])$
• for $i=1,\ldots , |x|$:
• $dp[0] = dp[0] \land (x[i] == z[i])$
• for $j= 1, \ldots, |y|$:
• $dp[j] = (dp[j] \and (x[i] == z[i + j])) \lor (dp[j-1] \land (y[j] == z[i + j]))$

3. Vertex cover

• 对于叶节点$i$，$dp[i]=0$

• 对于非叶节点$i$：

• 情形1对应选择根节点$i$，情形2对应选择根节点的直接子节点。