Solution: Let $e(n,m)$ be the minimum edit distance for the substring $X[1,n]$ and $Y[1,m]$.
deleted is the optimal solutionIf the $n$th character of $X$ is not the same as the $m$th character of $Y$, the optimal edit distance must be that of the substrings excluding this last character.
If the $n$th character of $X$ is not the same as the $m$th character of $Y$, it can be either added to $X$, changed from the last of $Y$ or added to $Y$. Hence we choose the option that would have had the least edits so far, and add one more edit to the count.
\[e(n,m) = \begin{cases} m & \text{if } n = 0 \\ n & \text{if } m = 0 \\ e(n-1, m-1) & \text{if } X_n = Y_m \\ 1 + \min\{e(n, m-1), e(n-1, m-1), e(n-1, m)\} & \text{otherwise } \\ \end{cases}\]Housekeeping:
Solution:
Edge cases:
Represent the array as a bitmask $\overline{x_1 x_2 \dots x_n}$, with $x_i = 1$ indicating presence in the partition
Let $\text{dp}(\overline{x_1 \dots x_n})$ be sum of all the elements in this mask’s partition (indicated by 1 bits), modulo $k$.
$\text{dp}(\overline{x_1\dots x_n}) = {\sum_{i=1}^m A[i] (x_i) \mod k}$
We want to find a partitioning using all elements in $S$, i.e., verify if $\text{dp}(1 \dots 1) = 0$.
Due to the additive property of congruence, $(x \mod k) + (y \mod k) = (x+y) \mod k$. Hence we have
# initialize dp (size 2^n)
dp = [-1 for i in range(2^n)]
for mask in range(2^n):
for i in range(n):
if (mask & (1 << i) == 0) and dp[mask] + a[i] <= target:
dp[mask | (1 << i)] = (dp[mask] + a[i]) % target
return dp[(1 << N) - 1] == 0
Note: ${Q, D, N, P} = {25, 10, 5, 1}$, as in quarter, dime, nickel, penny.
Solution:
Case 1: $i = N$ = 5. The solution $S$ must have 5 or more $P$. Since $S’ = S \setminus {5P} \cap {N}$ is smaller than $S$, this contradicts the optimality of $S$.
Case 2: $i = D$ = 10. The solution $S$ must have either:
Case 3: $i = Q$ = 25. The solution $S$ must have either:
Hence in all three cases, we proved by the cut and paste argument that the optimal solution should always pick the largest possible coin, as per the greedy algorithm.
Optimal Substructure Property: Let $P(n)$ be the problem of making $n$. Suppose the greedy solution first chooses $k$ cent coin. Let $S(n-k)$ be optimal solution to $P(n-k)$, and $S(n)$ be the optimal solution to $P(n)$. Then since cost(S) = cost(S′)+1, clearly optimal substructure is shown.
Solution: IN PROGRESS, TOO CONFUSING
Important: Since each even only takes 1 unit of time, an optimal scheduling can be back to back from $t = 0$, i.e. schedule is $x_i \rightarrow [0,1), x_j \rightarrow [1,2), \dots$ etc. Hence we only need to compare amongst the events that have the same $\lfloor t_i \rfloor$ time, as every other unit time will be scheduled.
extractMax $k$ from the queue and assign event $k$ to $t$.Greedy choice property: Consider an optimal solution $S$ in which $x+1$ events are scheduled at time $0, 1, \dots x$. Let event $k$ be the last job run in $S$.
Case 1: $\lfloor t_k \rfloor = \lfloor t_n \rfloor$. By our greedy choice: $g_k \geq g_n$
for i in range(n):
if time[i] >= T:
schedule i
T = time[i] + 1
skipped
Solution: For every last uncovered point, add a new interval and skipped the points that are covered by the new interval.
Greedy choice property: Let $S$ be an optimal solution. If $S$ places the leftmost interval at $[x, x+1]$, then $x \leq x_1$ by definition of our greedy choice (since $x_1$ is the first and smallest point to be checked).
If we were to replace $[x, x+1]$ with $[x_1, x_1+1]$ in $S’$, since there are no points between $[x, x_1)$, $S’$ is a valid solution with the same number of points as $S$.
Optimal substructure property: Let $P$ be the problem with optimal solution $S$. Suppose the greedy solution chooses $[x_1,x_1+1]$. Then the subproblem $P’$ finds an optimal solution $S’$ covering the points to the right of $x_1+1$. Then clearly cost(S) = cost(S′)+1, as $S$ includes $S’$.