力扣 1027. 最长等差数列 python AC

本文主要是介绍力扣 1027. 最长等差数列 python AC，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划

class Solution:def longestArithSeqLength(self, nums):size = len(nums)maxv = 0dp = [[1] * 1001 for _ in range(size)]for i in range(size):for j in range(i):d = nums[j] - nums[i] + 500dp[i][d] = max(dp[i][d], dp[j][d] + 1)maxv = max(maxv, dp[i][d])return maxv

定义dp[i][j]的状态为：到i为止公差为j的最长子序列长度

--dp：size行1001列（公差范围为[-500, 500]），默认值为1（长度至少为1）

--从0到size遍历i

  --从0到i遍历j

    --计算公差d = nums[j] - nums[i]（j在i前面，所以j-i），d范围为[-500, 500]，索引范围为[0, 1000]，最后要+500得到公差对应的索引

    --更新dp[i][d]（到i为止公差为d的最长子序列的长度）为dp[i][d]和dp[j][d] + 1的较大值

    --更新maxv为maxv和dp[i][d]的较大值

    (maxv:全局变量，用于保存所有结束位置和所有公差能够得到的最长子序列长度)

这篇关于力扣 1027. 最长等差数列 python AC的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---