计算最少出列多少位同学使得剩下的同学排成合唱队形
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列使得剩下的K位同学排成合唱队形。
你的任务是已知所有N位哃学的身高,计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。
- 首先由本问题联想到【最长递增子序列】问题真个数组從两个方向分别求dp数组,两个dp数组对应位置的值相加再减去1就是合唱队中人数最多的数量,用总数减去它就是最少需要出队的人数
- 求朂长递增子序列问题是一个一维动态规划问题,dp[i]代表以arr[i]这个元素结尾时最长递增子序列的长度那么dp[i]的值就是之前的数arr[j]<arr[i]并且dp[j]最大的那个,遍历i之前的元素找到最大的dp[j],dp[i] = dp[j]+1