最优化问题的解法分类

  1. DP。有最优子问题
  2. Scan。找出每个解的唯一标识,根据标识知道解的集合。挨个扫描所有标识,算出各个标识对应的解。扫描过程记录当前最优解。1758. Minimum Changes To Make Alternating Binary String
  3. Binary search。找出解集合的可能范围,但并非这个这个范围内的值都是合法的解。通常带有限制条件判断该值是不是合法的解。通过binary search找出最优的合法解。1760. Minimum Limit of Balls in a Bag

Leave a Reply