リートコード

[LeetCode] 413。算術スライス



413 Arithmetic Slices



質問： https://leetcode.com/problems/arithmetic-slices/description/

動的計画。



状態dp [i]：A [i]で終わる等間隔のサブインターバルの数を示します。

状態の初期化：dp [0] = dp [1] = 0。



状態遷移方程式：

A [i] -A [i-1] == A [i-1] -A [i-2]の場合、

  1. {A [i-2]、A [i-1]、A [i]}は、等間隔で増加するサブインターバルです
  2. {A [i-3]、A [i-2]、A [i-1]、A [i]}も等増分サブインターバルです。つまり、A [i] -A [i-1]の差は、dp [i-1]の増分差に等しくなります。

したがって、dp [i] = 1 + dp [i-1]です。



方程式：

if(A[i]-A[i-1] == A[i-1] - A[i-2]) dp[i] = dp[i-1] + 1 class Solution { public int numberOfArithmeticSlices(int[] A) { int[] dp = new int[A.length] for(int i = 2i<A.lengthi++){ if(A[i]-A[i-1] == A[i-1] - A[i-2]) dp[i] = dp[i-1] + 1 } int cnt = 0 for(int i = 2i<A.lengthi++) cnt+=dp[i] return cnt } }

最後の要件があるため、簡略化できます。

class Solution { public int numberOfArithmeticSlices(int[] A) { int[] dp = new int[A.length] int cnt = 0 for(int i = 2i<A.lengthi++){ if(A[i]-A[i-1] == A[i-1] - A[i-2]) dp[i] = dp[i-1] + 1 cnt+=dp[i] } return cnt } }

dp [i]は前のdp [i-1]のみを使用するため、さらに簡略化されます。

class Solution { public int numberOfArithmeticSlices(int[] A) { int[] dp = new int[2] int cnt = 0 for(int i = 2i<A.lengthi++){ if(A[i]-A[i-1] == A[i-1] - A[i-2]){ dp[1] = dp[0] + 1 cnt+=dp[1] dp[0] = dp[1] } else dp[0] = 0 } return cnt } }