Leetcode for Fun

Classical DP:

• f[house_i][k]: least cost if we set the k-^th mailbox at house_i
  • f[house_i][k] = min(f[last_house_j][k-1] + cost=sum(min(dist(house_mid, house_i), dist(house_mid, house_j)) for i < mid < j)
  • with pre-calculated cost, T(N) = O(NK * N).
• f[house_i][k]: least cost if we use k mailbox in range(i, n)
  • f[house_i][k] = f[house_j][k-1] + cost in range(i, j)
  • with pre-calculated cost, T(N) = O(N*N*K)

Key takeaways from the doc:
The library uses `insort` to insert or remove an element. Although `insort` is O(N) in theory because all the elements might have to shift, but based on the doc, `insort` is very fast in reality because some processor optimization. To prevent `insort` taking long time on a long List, the library split the List into multiple Lists (split when larger than a threshold and merge with neighbors if possible).

https://www.cnblogs.com/hujunyao37201/p/14647595.html

takeaway: calculate and then dp. Don’t do it at once.

https://blog.csdn.net/flyinghearts/article/details/5898183

https://leetcode-cn.com/circle/article/V5qkAa/

a “hash set” that only support query (with false-positive but high scalability)
 https://www.cnblogs.com/liyulong1982/p/6013002.html

• Original thought:
  • dp[light_length][left_on][right_on][#manually_turned_on] = dp[left_part][left_on][True][j] * dp[right_part][True][right_on][k]
  • which requires O(n*2*2*n*n*n)
• Key observation:
  • If we mark manually turned on lights as 1 and automatic ones as 0, one valid plan should look like 11101110111011
    • The first and last should be manually turned on
    • there will no two consecutive 0
  • In other words, we can split the array by 0s. And for each consecutive 1s, we can process them one block by one block
    • In a 1-block with k 1s, there are 2^(k-1) ways to turn it on. This can reduce the calculation
  • Final dp
    • dp[light_length][#manually_turned_on] = dp[light_length-last_block_len-1][#manually_turned_on-lask_block_len] * 2^(lask_block_len) * C(#manually_turned_on, lask_block_len)
• Takeaway:
  • think about the nature of the problem. Do rush into the dp.