Kod Leet

[LeetCode] 413. Potongan Aritmetik

413 Arithmetic Slices



soalan: https://leetcode.com/problems/arithmetic-slices/description/

Perancangan yang dinamik.



Nyatakan dp [i]: menunjukkan bilangan subintervals yang meningkat sama dengan A [i].



Permulaan keadaan: dp [0] = dp [1] = 0.



Persamaan peralihan negeri:

Sekiranya A [i] - A [i - 1] == A [i - 1] - A [i - 2],

  1. {A [i - 2], A [i - 1], A [i]} adalah subinterval yang sama rata
  2. {A [i - 3], A [i - 2], A [i - 1], A [i]} juga merupakan subinterval kenaikan yang sama. Maksudnya, perbezaan antara A [i] - A [i-1] sama dengan perbezaan tambahan dalam dp [i-1].

Jadi dp [i] = 1 + dp [i-1].



persamaan:

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 } }

Ia dapat dipermudahkan kerana syarat terakhir.

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 } }

Lebih dipermudahkan kerana dp [i] hanya menggunakan dp sebelumnya [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 } }