## 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 solution. Given and , 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

```
// 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
```