动态规划法解决合唱队形问题:最长上升/下降子序列详解
使用动态规划法求解合唱队形问题,需要将问题分解为两个子问题:最长上升子序列和最长下降子序列。最长上升子序列指的是身高递增的最长子序列,而最长下降子序列指的是身高递减的最长子序列。
我们可以使用两个数组,分别记录以每个同学为结尾的最长上升子序列和最长下降子序列的长度。
具体的步骤如下:
-
初始化最长上升子序列和最长下降子序列数组为 1,因为每个同学自己就是一个长度为 1 的递增/递减序列。
-
从第二个同学开始遍历,对于每个同学,分别向前遍历前面的所有同学,如果前面的同学身高比当前同学矮/高,那么这个同学可以接在前面的同学的递增/递减序列后面形成更长的递增/递减序列。更新最长上升子序列和最长下降子序列数组。
-
遍历结束后,最长上升子序列和最长下降子序列数组中的最大值之和减 1 即为最终答案(减 1 是因为最长上升子序列和最长下降子序列都包含了当前同学本身,所以重复计算了一次)。
例如,对于给定的身高序列 '176, 163, 150, 180, 170, 130, 167, 160',最长上升子序列和最长下降子序列数组分别为:
最长上升子序列数组:'1 1 1 2 2 1 3 2'
最长下降子序列数组:'1 2 3 1 2 1 2 3'
最终答案为 4,对应的合唱队形为:'163 150 130 160'。
原文地址: https://www.cveoy.top/t/topic/oHyo 著作权归作者所有。请勿转载和采集!