解题思路
- 先对height升序排序,同height的weight降序排序(利用zip组合列表后排序);
- 问题转为化为求weight的最长上升子序列(Longest Increasing Subsequence, LIS);
代码
class Solution:
def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
if len(height) ==1:
return 1
hw = list(zip(height, weight))
hw.sort(key=lambda x:[x[0],-x[1]])
# hw = [i[1] for i in hw]
_,hw = zip(*hw)
dp = [hw[0]]
for i in range(1,len(hw)):
is_replace = False
for j in range(len(dp)):
if dp[j] >= hw[i]:
dp[j] = hw[i]
is_replace = True
break
if not is_replace:
dp.append(hw[i])
return len(dp)
参考
讲的很好
https://leetcode-cn.com/problems/circus-tower-lcci/solution/c-onlogn-by-lzn27/
动态规划(DP)
https://www.zhihu.com/question/23995189
留言