linear DP
Work in Progress
Summary
Top-down
Solve(i):
if i is a base state:
return BASE(i)
if Memo[i] != UNSEEN:
return Memo[i]
answer = IDENTITY
for each option o in OPTIONS(i):
j = NEXT(i, o) // j > i
candidate = STEP(i, o, Solve(j))
answer = COMBINE(answer, candidate)
Memo[i] = answer
return answer
Botton-up
Initialize base states in DP
for i = n down to 1:
DP[i] = IDENTITY
for each option o in OPTIONS(i):
j = NEXT(i, o)
candidate = STEP(i, o, DP[j])
DP[i] = COMBINE(DP[i], candidate)
return DP[target]
Concept
Linear DP
Weighted Interval Scheduling
- maximize the weights of the selected intervals
- greedy scheduling fails when weights are included
- linear DP
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| Best value after skipping | Skip interval |
Top-down
WIS()
sort intervals by start time s_i
for i = 1...n
visited[i] <- false
answer[i] <- unknown
next[i] <- min{j > i : s_j > f_i} // binary search, O(log n)
return opt(1)
opt(k)
if visited[k] return answer[k]
visited[k] <- true
answer[k] <- max{w_k + opt(next[k]), opt(k+1)}
return answer[k]
Bottom-up
WISBottomUp()
opt[n + 1] <- 0
next <-
for k = n...1
opt[
Longest Increasing Subsequence (LIS)
Problem
- input:
integers - output: length
of the longest increasing subsequence of - LIS definition: max
for some such that
Naive
Recursive
- length of LIS that starts at index
L(i):
out <- 0
for j = i+1 ... n:
if a[j] > a[i]:
out <- max(out, L(j))
return 1 + out
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| Stop at | ||||
| Bottom-up |
for i = n down to 1:
D[i] = 1
next[i] = NIL
for j = i+1 to n:
if A[j] > A[i] and 1 + D[j] > D[i]:
D[i] = 1 + D[j]
next[i] = j
return max D[i] // return 0 if input is empty
Correctness
Time complexity
Improved
pos[l] = index of largest a_i for which L(i) = l
Claim: a[pos[1]] > a[pos[2]] > a[pos[3]] > … > a[pos[m]]
so we can do binary search, yippee
Application
Codeforces: Vacations
- linear DP
- tabulate the max number of active days if either resting, contest or sport
cpp
vector<array<int, 3>> dp(n + 1, {0, 0, 0}); // number of active days after i days, if
// on the ith day, rest, contest or sport
for (i = 1; i <= n; i++) {
const auto &prev = dp[i - 1];
// 1st col is max of previous row
dp[i][0] = max(prev[0], max(prev[1], prev[2]));
// 2nd col is max of previous row, or +1 if contest can be done and not consequtive
dp[i][1] = a[i - 1] & 1 ? max(prev[0] + 1, prev[2] + 1) : dp[i][0];
// 3rd col is max of previous row, or +1 if sport can be done and not consequtive
dp[i][2] = a[i - 1] & 2 ? max(prev[0] + 1, prev[1] + 1) : dp[i][0];
}
cout << n - max(dp[n][0], max(dp[n][1], dp[n][2])) << "\n";
return 0;