Reduce Time Complexity in DP

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

 TrickDifficulty
LC 1027. Longest Arithmetic SequenceDP in Linear Structures + Arithmetic6 points
LC 446. Arithmetic Slices II - SubsequenceDP in Linear Structures + Arithmetic6 points
LC 1187. Make Array Strictly IncreasingDP in Linear Structures + Greedy6 points
LC 1420. Build Array Where You Can Find The Maximum Exactly K ComparisonsDP counting + Prefix Sum6 points
LC 514. Freedom TrailDP in Linear Structures + Greedy6 points
LC 1434. Number of Ways to Wear Different Hats to Each OtherDP Knapsack + State Compression6-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

Leave a Reply

Your email address will not be published. Required fields are marked *