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
StateMeansNeedDecisionCombination
is the maximum weight of compatible intervals chosen from .Best value after skipping , and best value after taking : , .Skip interval , or take it and jump to the first compatible interval.. Base: .

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
StateMeansNeedDecisionCombination
is the length of a longest increasing subsequence starting at . for every with .Stop at , or choose which valid position comes next.. Final answer: .
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
RCG1320000011112222222
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;