【每日一题Day185】LC1027最长等差数列 | dp

最长等差数列【LC1027】

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

最近还挺顺手的
2023/04/22

• 思路：枚举选哪个

  每遇到一个数$nums[i]$，我们需要枚举这个数和前面每个数组成的等差子序列的情况（差值和长度），来更新以$nums[i]$结尾的差值为$j$的子序列的长度

  1. 确定dp数组（dp table）以及下标的含义

     dp[i][j]:以nums[i]为末尾的差为j的等差序列的最长长度

  2. 确定递推公式

     对于dp[i][j]，枚举前一位$arr[j]$，求出由这$nums[j],nums[i]$组成的等差序列的差值$div$，dp[i][k]的状态由dp[j][k]更新，状态转移方程为
     $$dp[i][j]=max(dp[i][k],dp[j][k]+1)$$

  3. 如何初始化

     初始时，子序列只包含当前数字，因此dp数组均为1（也可以初始化为0，最后将答案+1）

  4. 确定遍历顺序

     从小到大枚举$i$，然后从大到小枚举$j$

  5. 举例推导dp数组

• 实现

  由于差值可能为负数，最小差值为-500，因此需要统一+500

  class Solution {public int longestArithSeqLength(int[] nums) {// dp[i][j] 以nums[i]为末尾的差为j的等差序列的最长长度 【负数+500】int n = nums.length;int res = 0;int[][] dp = new int[n][1010];for (int i =  0; i < n; i++){Arrays.fill(dp[i], 1);}for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){int div = nums[i] - nums[j] + 500;dp[i][div] = Math.max(dp[i][div], dp[j][div] + 1);res = Math.max(res, dp[i][div]);}}return res;}
  }
  

  • 复杂度

    • 时间复杂度： O ( n C + n 2 ) O(nC+n^2) O(nC+n2)，$n$为数组长度，$C$为定义的状态空间大小，初始化需要的时间复杂度为$O(nC)$，动态规划的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
    • 空间复杂度：$O(nC)$

美味小吃