Dynamic Programming Assignment

Sajanjit Singh Brar (25M2151)

CS 601: Algorithms and Complexity

October 27, 2025

Question 1
Word Segmentation with Maximum Likelihood.

Solution:
Idea. Let dp[i] be the maximum total score achievable by segmenting the prefix S[1 . . . i]. If
the last word of an optimal segmentation of S[1 . . . i] is S[j + 1 . . . i] for some 0 ≤ j < i, then


dp[i] = max dp[j] + score(S[j + 1 . . . i]) ,
0≤j<i

with base dp[0] = 0. Store backpointers prev[i] to reconstruct the segmentation.

Recurrence.
dp[0] = 0,


dp[i] = max dp[j] + score(S[j + 1 . . . i]) , i = 1, . . . , n,
0≤j<i

Complexity. If score(·) can be computed in O(1) (lookup / precomputed table), the nested
loops give O(n2 ) time and O(n) space.
Correctness. We can prove by induction on i that dp[i] equals the optimal segmentation
score for S[1 . . . i]:
• Base: dp[0] = 0 is correct.
• Inductive step: any optimal segmentation of S[1 . . . i] ends with some S[j + 1 . . . i]; its
score equals the optimal score of S[1 . . . j] plus score(S[j + 1 . . . i]). By the inductive
hypothesis this equals dp[j] + score(S[j + 1 . . . i]). Taking the maximum over all choices
of j gives dp[i].
Thus the DP computes an optimal value and the prev pointers recover an optimal segmenta-
tion.

1
Question 2
Minimum Time to Collect All Coins in a Grid.

Solution:
Distance Matrix. Let c be the number of coins and let s = (0, 0) denote the start. Enumerate
the c coin positions p1 , . . . , pc and index the start as p0 = s. For each t ∈ {0, 1, . . . , c} run
BFS from pt on the grid (treating obstacles as blocked) to obtain shortest-path distances to
every cell; extract the pairwise distances

dist[t, u] = shortest-path length from pt to pu , 0 ≤ t, u ≤ c.

DP formulation. Index coins by i ∈ {1, . . . , c} Use a bitmask mask ∈ {0, . . . , 2c − 1} to

represent which coins have been visited; bit i corresponds to coin i. Define

dp[mask][i]

to be the minimum time (number of steps) to start at s, visit exactly the set of coins indicated
by mask, and finish at coin i (where bit i is set in mask).

Bitmask notation: 1«i. In the DP formulation we use bitmasks to represent sets of coins;
the expression 1«i denotes the bitwise left shift of the integer 1 by i positions.

1«i = 2i ,

so it produces an integer whose binary representation has a single 1 in position i (positions

are counted from 0).

• Set bit i (mark coin i visited): mask |= (1«i) (equivalently mask ← mask ∨ 2i ).

• Test if bit i is set: if (mask & (1«i)) ... (true when coin i is already visited).

• Clear bit i: mask &= (1«i) (remove coin i from the set).

In our DP we frequently write mask & (1 ≪ i) to check whether coin i is included in mask, and
we use 1«i to refer to the singleton set containing only coin i (e.g. the base case dp[1 ≪ i][i]).
Base case. For each coin index i,

dp[1 ≪ i][i] = dist[0, i + 1],

i.e. cost to go from start p0 to coin pi+1 .

Transition. For any mask with bit i set and mask ̸= (1 ≪ i),


dp[mask][i] = min dp[mask \ {i}][j] + dist[j + 1, i + 1] ,
j∈mask, j̸=i

2
where indices in dist[·, ·] use 0 for start and 1 . . . c for the c coins.
Final answer. Let ALL = (1 ≪ c) − 1. The minimal total time to visit all coins and return
to the start is

min dp[ALL][i] + dist[i + 1, 0] .
i=0,...,c−1

Complexity. Each BFS on the n × n grid takes O(n2 ), and we run c + 1 BFSs, so O(c n2 ).
DP time is O(c2 2c ) and space O(c2c ). Total time O(c n2 + c2 2c ) and total space O(n2 + c2c ).

Correctness. BFS computes exact shortest-path distances between the important vertices.
The DP uses optimal substructure: an optimal tour that visits set mask and ends at coin i
must consist of an optimal subpath that visits mask \ {i} and ends at some coin j, followed by
the edge j → i. Therefore the recurrence is correct and induction on |mask| shows dp[mask][i]
stores the minimum cost for that subproblem.

References

1. HackerEarth — Bitmasking tutorial.

2. Quang Nguyen, “Travelling Salesman Problem and Bellman-Held-Karp Algorithm”

[Link] richard/teaching/s2020/[Link].

Question 3
Expected Longest Streak in a Markov Chain.

Solution:
Problem. We have N games. The first game is won with probability P0 . For t ≥ 2 the win
probability for game t depends on the previous outcome:

Pr(win at t | previous was Win) = PW , Pr(win at t | previous was Loss) = PL .

Let L be the length of the longest consecutive winning streak during the N games. We wish
to compute E[L].

Probability DP. Define the probability

P [t][m][r][s]

as the probability that after exactly t games:

• the longest winning streak observed so far is m,

3
 • the current ongoing winning streak length is r (so r ≥ 0; in particular r = 0 if the last
game was a Loss),

• the result of game t is s ∈ {W, L} (Win or Loss).

Note that 0 ≤ r ≤ m ≤ t and r > 0 iff s = W ; when s = L we always have r = 0.

Initialization (base case, t = 1). The distribution after the first game is:

P [1][1][1][W ] = P0 ,
P [1][0][0][L] = 1 − P0 ,

and all other P [1][·][·][·] are zero.

Transition (for t ≥ 2). Consider a state at time t − 1 with parameters (m, r, s) and
probability P [t − 1][m][r][s]. Let

PW if s = W,
(
pwin (s) =
PL if s = L.

When the next game (game t) is played there are two cases:
(1) Next game is a Win (occurs with probability pwin (s)). Then the new ongoing streak
becomes r′ = r + 1, and the new maximum becomes m′ = max(m, r′ ). The new last-result is
W . Thus

P [t][ m′ = max(m, r + 1) ][ r + 1 ][W ] + = P [t − 1][m][r][s] · pwin (s).

(2) Next game is a Loss (occurs with probability 1 − pwin (s)). The ongoing winning streak
resets to r′ = 0, the maximum remains m′ = m, and the new last-result is L. Thus


P [t][ m ][ 0 ][L] + = P [t − 1][m][r][s] · 1 − pwin (s) .

Apply these updates for every valid previous (m, r, s) at time t − 1.

The distribution of L. After processing all N games, the probability that the longest
streak equals k is
k
X

Pr(L = k) = P [N ][k][r][W ] + P [N ][k][r][L] ,
r=0

Finally
N
X
E[L] = k · Pr(L = k).
k=0

Pseudocode.

4
Algorithm 1 Compute distribution of longest winning streak
Require: N, P0 , PW , PL
1: Initialize all probabilities P [t][m][r][s] ← 0 for valid indices
2: /* Base case: t = 1 */
3: P [1][1][1][W ] ← P0
4: P [1][0][0][L] ← 1 − P0
5: for t ← 2 to N do
6: Zero out layer P [t][·][·][·]
7: for each feasible (m, r, s) with P [t − 1][m][r][s] > 0 do
8: q ← P [t − 1][m][r][s]
9: if s = W then
10: p ← PW
11: else
12: p ← PL
13: end if
14: r′ ← r + 1
15: m′ ← max(m, r′ )
16: P [t][m′ ][r′ ][W ] += q · p
17: P [t][m][0][L] += q · (1 − p)
18: end for
19: end for
20: /* After N games: compute distribution of longest run L */
21: for k ← 0 to N do
Pr(L = k) ← kr=0 P [N ][k][r][W ] + P [N ][k][r][L]
P

22:
23: end for
XN
24: return distribution Pr(L = k) for k = 0 . . . N and E[L] = k Pr(L = k)
k=0

Complexity. For a fixed t the number of feasible (m, r) pairs is O(t2 ) (since 0 ≤ r ≤ m ≤ t).
Updating from t − 1 to t therefore requires O(t2 ) operations; summing t = 1 . . . N yields a
total time complexity O(N 3 ). Space to store the full table P [t][m][r][s] for all t would be
O(N 3 ) but we can reduce space to O(N 2 ) by keeping only the current layer t and previous
layer t − 1 (rolling array), since transitions only depend on t − 1.

Correctness. The DP explicitly tracks the complete probabilistic state required to determine
future evolution: the number of games played t, current streak length r, and the maximum m
observed so far. Transitions are exact because the Markov assumption makes the next-game
win probability a function only of the previous outcome s.

Example. Let N = 3, P0 = 0.4, PW = 0.6, PL = 0.3.

Base (t=1). After the first game we have two possible states:
P [1][1][1][W ] = P0 ,
P [1][0][0][L] = 1 − P0 .

5
Step t=1 → t=2 (apply transitions). We update each nonzero t = 1 state using the rule
(
PW s = W,
pwin (s) =
PL s = L.

From P [1][1][1][W ] (probability P0 ):

• If game 2 is a win (prob. PW ): current run becomes r′ = 2, max m′ = max(1, 2) = 2.

So
P [2][2][2][W ] += P0 · PW .

• If game 2 is a loss (prob. 1 − PW ): current run resets r′ = 0, max stays m′ = 1. So

P [2][1][0][L] += P0 · (1 − PW ).

From P [1][0][0][L] (probability 1 − P0 ):

• If game 2 is a win (prob. PL ): r′ = 1, m′ = max(0, 1) = 1:

P [2][1][1][W ] += (1 − P0 ) · PL .

• If game 2 is a loss (prob. 1 − PL ): r′ = 0, m′ = 0:

P [2][0][0][L] += (1 − P0 ) · (1 − PL ).

After these updates, the only potentially nonzero t = 2 states (symbolically) are

P [2][2][2][W ], P [2][1][0][L], P [2][1][1][W ], P [2][0][0][L],

each given by the expressions above.

Step t=2 → t=3. Now apply the same transition rule to every nonzero t = 2 state. Write
q for the probability of a given t = 2 state; if its last result is s then its next-win probability
is pwin (s). For each state (m, r, s) at t = 2 we do:

• If next is Win (prob. pwin (s)): update

P [3][ max(m, r + 1) ][ r + 1 ][W ] += q · pwin (s).

• If next is Loss (prob. 1 − pwin (s)): update

P [3][ m ][ 0 ][L] += q · (1 − pwin (s)).

Concretely, applying this to each of the four symbolic t = 2 states yields a collection of
t = 3 states such as

P [3][3][3][W ], P [3][2][2][W ], P [3][2][0][L], P [3][1][1][W ], P [3][1][0][L], P [3][0][0][L],

6
with each entry being the sum of the appropriate contributions of the form (prob. at t =
2) × (transition probability).
The distribution and expectation. After processing t = 3 we obtain Pr(L = k) by
summing over all states with maximum m = k:
X

Pr(L = k) = P [3][k][r][W ] + P [3][k][r][L] , k = 0, 1, 2, 3.
r≥0

Finally compute the expectation

3
X
E[L] = k · Pr(L = k).
k=0

Question 4
Balancing Work and Leisure Before Exams.

Solution:
Setup. Input: integer n and temperatures t1 , . . . , tn (each ti may be positive or negative).
Choice each day: go outdoors and gain ti to mood, or study (indoor) and gain 0. Constraint:
never more than two consecutive outdoor days. Goal: maximize total mood gain over n days.
DP. For i = 1, . . . , n define three values

dp[i][0], dp[i][1], dp[i][2],

where

• dp[i][0] = maximum total mood after day i when day i is study (i.e. there are 0
consecutive outdoor days ending at i),

• dp[i][1] = maximum total mood after day i when day i is outdoor and it is the 1st
consecutive outdoor day,

• dp[i][2] = maximum total mood after day i when day i is outdoor and it is the 2nd
consecutive outdoor day.

Recurrence. Initialize (before day 1) dp[0][0] = 0 and dp[0][1] = dp[0][2] = −∞. For
i = 1, . . . , n:

dp[i][0] = max dp[i − 1][0], dp[i − 1][1], dp[i − 1][2] ,
dp[i][1] = dp[i − 1][0] + ti ,
dp[i][2] = dp[i − 1][1] + ti .

7
Base cases. dp[i][0] corresponds to choosing study on day i; it may follow any state on day
i − 1. dp[i][1] corresponds to choosing outdoor on day i while day i − 1 was study. dp[i][2]
corresponds to choosing outdoor on day i while day i − 1 was exactly one outdoor day.
Answer. The optimal total mood after all days is


max dp[n][0], dp[n][1], dp[n][2] .

To recover the actual plan (which days are outdoor vs study) store for each dp[i][k] a parent
pointer to which of dp[i − 1][·] produced the maximum; then backtrack from the maximizing
state at i = n to i = 1.
Pseudocode (iterative, O(n) time).

Algorithm 2 Maximize mood with at most two consecutive outdoor days

Require: n, array t[1..n]
1: dp0 ← 0, dp1 ← −∞, dp2 ← −∞ ▷ states for day 0
2: for i ← 1 to n do
3: new0 ← max(dp0, dp1, dp2) ▷ choose study on day i
4: new1 ← dp0 + t[i] ▷ outdoor after a study
5: new2 ← dp1 + t[i] ▷ outdoor after exactly one outdoor day
6: dp0 ← new0, dp1 ← new1, dp2 ← new2
7: end for
8: return max(dp0, dp1, dp2)

Complexity. For each day we perform a constant number of operations, hence the algorithm
runs in O(n) time. With the update algorithm above, we store only O(1) state (three numbers)
so space is O(1).
Correctness. Let the recurrence values dp[i][k] be defined as above. We prove by induction
on i that dp[i][k] equals the maximum possible total mood over days 1 . . . i among schedules
whose last-day pattern corresponds to k consecutive outdoor days (with k = 0, 1, 2). Base
i = 0 holds by initialization. For the inductive step, any optimal schedule for the first i days
that ends in pattern k must arise by taking an optimal schedule for the first i − 1 days that
ends in an allowed predecessor pattern and then making the decision on day i (study or
outdoor) that gives the state k. The recurrence picks the best predecessor pattern, therefore
dp[i][k] is optimal. Finally, taking the maximum over k at day n gives the optimal schedule.

Question 5
The Mentor Allocation Challenge.

8
Solution:
Problem. There are 3n students, each with three nonnegative integer gains (gi , di , ri ) for the
three sessions: Graphs (G), Dynamic Programming (D), and Greedy (R). We must assign
exactly n students to each session such that:

• each student is assigned to exactly one session,

• no student is assigned to a session where their gain is 0,

• the total learning gain (sum of assigned gains) is maximized.

If no valid assignment exists, report that the allocation is infeasible.

DP formulation. We process students sequentially and track how many have been assigned
to the first two sessions (G and D). The number of students in the third session (R) is implied.
Let
(
maximum total gain after considering the first i students,
DP[i][a][b] =
with a assigned to Graphs and b assigned to DP,

and where the number of students assigned to Greedy is c = i − a − b.

A state is valid only if 0 ≤ a, b, c ≤ n. If any of these counts exceeds n or becomes
negative, the state is infeasible and DP[i][a][b] = −∞.

Base case.
DP[0][0][0] = 0, DP[0][a][b] = −∞ for all other (a, b).

Transition (for student i with gains (gi , di , ri )). From each feasible state (i, a, b) we can
assign student i to one of the three sessions:

If gi > 0 and a < n : DP[i + 1][a + 1][b] = max DP[i + 1][a + 1][b], DP[i][a][b] + gi ,

If di > 0 and b < n : DP[i + 1][a][b + 1] = max DP[i + 1][a][b + 1], DP[i][a][b] + di ,

If ri > 0 and (i − a − b) < n : DP[i + 1][a][b] = max DP[i + 1][a][b], DP[i][a][b] + ri .

Skip any update where the relevant gain is zero or the target group is already full.

Answer. After processing all 3n students, the maximum achievable total gain is

DP[3n][n][n] ,

provided this value is finite. If DP[3n][n][n] = −∞, then no feasible assignment exists.

Complexity.

9
 • There are O(n3 ) valid states (i, a, b) and constant-time updates per state, so total time
is O(n3 ).
• We can store only two layers (i and i+1) at a time, reducing space to O(n2 ).

Pseudocode.

Algorithm 3 Mentor Allocation DP

Require: n, arrays g[1..3n], d[1..3n], r[1..3n]
1: Initialize cur[0..n][0..n] ← −∞, cur[0][0] ← 0
2: for i ← 1 to 3n do
3: Initialize next[0..n][0..n] ← −∞
4: for a ← 0 to n do
5: for b ← 0 to n do
6: val ← cur[a][b]
7: if val = −∞ then continue
8: end if
9: c←i−1−a−b
10: if g[i] > 0 and a < n then
11: next[a+1][b] ← max(next[a+1][b], val + g[i])
12: end if
13: if d[i] > 0 and b < n then
14: next[a][b+1] ← max(next[a][b+1], val + d[i])
15: end if
16: if r[i] > 0 and c < n then
17: next[a][b] ← max(next[a][b], val + r[i])
18: end if
19: end for
20: end for
21: Swap(cur, next)
22: end for
23: return cur[n][n]

Correctness. We prove by induction on i that for each feasible pair (a, b), DP[i][a][b] equals
the maximum total gain achievable after considering the first i students and assigning exactly
a to Graphs and b to DP (with c = i − a − b to Greedy).
• Base case: i = 0 is correct by initialization.
• Inductive step: any valid partial assignment of the first i + 1 students with counts (a′ , b′ )
must be formed by adding student i to one of the three groups, giving predecessor counts
that the recurrence outputs. The recurrence keeps the best of all such transitions.
Therefore DP[3n][n][n] is the optimal total gain.

10
Question 6
Analyzing Connectivity in a Restricted Social Network.

Solution:
Problem. We are given n people labeled 0, 1, . . . , n − 1. A list of restrictions specifies pairs
[x, y] who must never belong to the same connected component. A list of requests specifies
friend connections [u, v] that appear sequentially. For each request, we must determine whether
it can be accepted (true) without violating any restriction. If accepting it would cause any
restricted pair to become connected, the request must be rejected (false). Friendships are
permanent: once a request is accepted, its endpoints remain connected for all future requests.

Approach: Disjoint Set Union (Union–Find).

We maintain connected components using a Disjoint Set Union (DSU) data structure.
For each component (identified by its root), we also maintain a set forbid[r] containing all
people who are not allowed to share a component with any member of that component.

• Initially, each person is its own component: parent[i] = i.

• For every restriction pair (x, y), insert y into forbid[x] and x into forbid[y].

When processing a request (u, v):

1. Let ru = find(u) and rv = find(v).

2. If ru = rv , the request is automatically safe (true).

3. Otherwise, check for a conflict:

The request is invalid if there exists some restricted person x ∈ forbid[ru ]

with find(x) = rv , or vice versa.

4. If a conflict is found, reject the request (false); otherwise, accept it (true) and merge
the two components with union(ru , rv ).

5. After merging, combine the forbidden sets:

forbid[new_root] ← forbid[ru ] ∪ forbid[rv ].

Complexity.

• DSU operations (find/union) take O(α(n)) amortized time.

• Using small-to-large merging of forbidden sets, the total cost of merging and conflict
checking across all requests is O((n + R + Q) log n) in practice, where R is the number
of restricted pairs and Q is the number of requests.

11
Space usage is O(n + R).

Pseudocode.

Algorithm 4 Process Restricted Friend Requests

Require: n, list restrictions, list requests
1: Initialize DSU with parent[i]=i, size[i]=1
2: Initialize forbid[i] = ∅ for all i
3: for each (x, y) in restrictions do
4: forbid[x].add(y), forbid[y].add(x)
5: end for
6: for each request (u, v) in requests do
7: ru ← find(u), rv ← find(v)
8: if ru = rv then
9: accept ← true
10: else
11: accept ← true
for each x ∈ forbid[ru ]: if find(x) = rv then accept←false
for each x ∈ forbid[rv ]: if find(x) = ru then accept←false
12: if accept then
13: new_root ← union(ru , rv )
14: Merge smaller forbidden set into larger: forbid[new_root] ← forbid[ru ] ∪
forbid[rv ]
15: end if
16: end if
17: Record result (true/false)
18: end for

Correctness.

• Invariant: for each DSU root r, forbid[r] contains exactly those people who cannot be
in the same component as any member of r.

• Each merge updates both the DSU structure and the forbidden sets so that the invariant
remains true.

• A request is rejected if and only if its endpoints belong to components that would merge
two mutually forbidden persons into one set.

Hence, the algorithm always accepts requests that are valid and rejects those that would
violate a restriction.

12