Reduce Time Complexity in DP – FighterNan's Blog

Summary

In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states.

OJ

	Trick	Difficulty
LC 1027. Longest Arithmetic Sequence	DP in Linear Structures + Arithmetic	6 points
LC 446. Arithmetic Slices II - Subsequence	DP in Linear Structures + Arithmetic	6 points
LC 1187. Make Array Strictly Increasing	DP in Linear Structures + Greedy	6 points
LC 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons	DP counting + Prefix Sum	6 points
LC 514. Freedom Trail	DP in Linear Structures + Greedy	6 points
LC 1434. Number of Ways to Wear Different Hats to Each Other	DP Knapsack + State Compression	6-7 points

Details

LC 1027. Longest Arithmetic Sequence

It is not difficult to get the following O(n^2logn) solution.

alg[i][j] = 
 alg[j][pos], let num=2*nums[j]-nums[i] in pos = lower_bound(num_to_pos[num], j + 1)

However, if we adopt the following state definition, the complexity reduces to O(n^2). A tricky part is that the difference seems to be of O(n^2) complexity for an array. But here, the difference for each i will only be O(n) because of j > i.

// vector<unordered_map>
alg[i][diff]: sequence starting at i with different==diff

let diff=nums[j]-nums[i] in 
  alg[i][diff] = max {
   diff in alg[j] ? alg[j][diff] + 1 : 2; for j in [i+1, n-1]}

LC 446. Arithmetic Slices II – Subsequence

It is not difficult to get the following O(n^3) solution.

alg[i][j] = 
   sum{ alg[j][k] == 0 ? 1 : alg[j][k] + 1 if nums[k] == 2 * nums[j] - nums[i] for k in [j+1, n-1] }
// alg[j][k] + 1 because {nums[i] : sequence[j][k]} + {nums[i], nums[j], nums[k]}

However, if we use the same arithmetic difference technique, we can reduce the complexity to O(n^2). An annoying thing here is that we only count subsequences of length >= 3. We could use two tables to store subsequences of different lengths.

 // sequence length > 2 
alg[i][diff] = let diff = alg[j] - alg[i] in 
    sum{ {diff in alg[j] ? alg[j][diff] : 0} + {diff in alg2[j] ? alg2[j][diff] : 0} for j in [i + 1, n - 1]}
    result += sum {alg[i].vals}
    
// sequence length == 2
alg2[i][diff] = let diff = alg[j] - alg[i] in 
    alg2[i][diff]++ for j in [i + 1, n - 1]

LC 1187. Make Array Strictly Increasing

It is not difficult to get the following O(mnlog(n)) solution.

// prev is in arr1[i - 1]::arr2
alg[i][prev] = 
  1. if arr1[i] > prev
     1) alg[i + 1][arr1[i]] 
     // greadily choose the smallest larger one
     2) 1 + alg[i + 1][j], j = upper_bound(arr2, prev); 
  2. if arr1[i] <= prev
     1) 1 + alg[i + 1][j], j = upper_bound(arr2, prev);

However, since prev is always in arr1[i - 1]::arr2, we could solve the problem in O(mn) by enumerating the index of prev. The advantage of using an index is that the next greater element is index+1.

// starting at i, previous is arr2[j], if j == n, it means it is arr1[i - 1]
alg[i][j] = 
 1. if arr1[i] > arr2[j] && j in [0, n - 2] 
     1) alg[i + 1][n]
     2) 1 + alg[i + 1][j + 1]
 2. if arr1[i] <= arr2[j] && j in [0, n - 2] 
     1) 1 + alg[i + 1][j + 1]
 3. if arr1[i] > arr1[i - 1] && j == n
     1) alg[i + 1][n] 
     2) alg[i + 1][k], k = arr2.upper_bound(arr1[i]) - arr2.begin()
 4. if arr[i] <= arr1[i - 1] && j == n
     1) alg[i + 1][k], k = arr2.upper_bound(arr1[i]) - arr2.begin()
 5. if arr1[i] > arr2[j] && j == n - 1
     1) alg[i + 1][n]
 6. othercases will be -1

LC 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

It is not difficult to get the O(nm^2K) solution.

alg[i][k][prev_max] = sum {
  1. prev_max * alg[i + 1][k][prev_max]
  2. alg[i + 1][k + 1][j] for j in [prev_max + 1, m]

// alg[n][k][j] = 1 for j in [1, m]

However, as we could see, the nested loop which enumerates the next prev_max could be achieved by the prefix sum technique. To make implementation easier, I use another table to store prefix sum, which reduces the complexity to O(nmK).

alg[i][k][prev_max] = sum {
  1. prev_max * alg[i + 1][k][prev_max]
  2. alg2[i + 1][k + 1][prev_max+1] == sum {alg[i + 1][k + 1][j] for j in [prev_max + 1, m]}

// alg[n][k][j] = 1 for j in [1, m]
    
// alg2[i][k][m] = alg[i][k][m]
alg2[i][k][j] = alg[i][k][j] + alg2[i][k][j + 1]

LC 514. Freedom Trail

It is not difficult to get the O(nm^2) solution.

// ring m, key n
// ch_to_index is for ring
alg[j][i]
 = cost(i, k) + alg[j + 1][k] for k in ch_to_index[key[j]]]

Actually, given any key[j] and the current position i at ring, we could greedily choose two same characters in ring: the nearest right and the nearest left. We could preprocess this in O(26mlogm) time. Then the time complexity reduces to O(nm).

alg[j][i]
 = min(cost(i, left) + alg[j + 1][left], cost(i, right) + alg[j + 1][right])

LC 1434. Number of Ways to Wear Different Hats to Each Other

It is not difficult to get the $O(n_{people}\times n_{hat}\times2^{n_{hat}})$ solution. Given $n_{people}=10$ and $n_{hat}=40$ , this solution will get TLE.

// n_people; n_hat 
// i here is the index of people
alg[i][visited] = 
  alg[i + 1][visited | num_to_hat_index[hat]] if num_to_hat_index[hat] not in visited && hat in hats[i] for hat in [0, 40]

We could think on the other hand: let the hat choose people. Then the complexity becomes $O(n_{people}\times n_{hat}\times2^{n_{people}})$

// i here is the index of hat
alg[i][visited]
  1. alg[i + 1][visited | (1 << j)] if (1 << j) & visited == 0 && distinct_hat[i] in people_to_hat_set[j] for j in [0, n - 1] 
  2. alg[i + 1][visited] // ith hat could not be chosen
// alg[n_hat][(1 << n_people) - 1] = 1