2022-11-27.md

题目

446. Arithmetic Slices II - Subsequence

Given an integer array nums, return the number of all the arithmetic subsequences of nums.

思路

dp[i][diff] = sum(dp[j][diff]+1), j = [0,i)

代码

var numberOfArithmeticSlices = function(nums) {
  let sum = 0
  const dp = []
  for (let i = 0; i < nums.length; i++) {
    dp[i] = []
    for (let j = 0; j < i; j++) {
      const diff = nums[j] - nums[i]
      sum += dp[j][diff] || 0
      dp[i][diff] = (dp[i][diff] || 0) + (dp[j][diff] || 0) + 1
    }
  }
  return sum
};