DP
动态规划是用多项式解决问题的方式，一般用来解决不能改变数据顺序求Max/Min值，最大最小路径，多少种解决方法之类的问题。需要观察发现子问题的状态和状态转移方程，总结出多项式继而解决问题。
MIT DP 第一节课的总结：
1, Memorization + recursion:
在使用recursion的同时用dict记录每次recursion的结果，这样就不用重复计算相同的状态。复杂度为o(n)
2, bottom up:
直接使用dict保存状态，不在使用recursion，类似于拓扑sort，后面的值通过读取前面的值求得。也是O(N)，但是是constant space。
413. Arithmetic Slices
Add to List
Question
Editorial Solution
My Submissions
- Total Accepted: 10203
- Total Submissions:
- Difficulty: Medium
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
Hide Company Tags
思路：最straightforward的做法就是两个指针控制窗口大小，最小的窗口是3，如果j+1和j的差与j和i的差相等，那么j就向右移一个，res+=1；否则i就向右移一个。但这样的做法是O(n2)的复杂度。优化方法就是用dp，last记录上一次的状态，如果当前的差值和之前的差值相等，那么说明last+=1，即当前组合是正确的，否则就将last置零。每一次判断结束都res+=last
class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
if len(A) < 3:
return 0
# i = 0
# res = 0
# l = len(A)
# while i < l - 2:
# j = i + 1
# diff = A[j] - A[i]
# while j + 1 < l:
# if A[j+1] - A[j] == diff:
# res += 1
# j += 1
# else:
# break
# i += 1
# return res
'''math的方法，不太懂'''
# if len(A) <= 2:
# return 0
# i, count, head, prediff = 2, 0, 0, A[1]-A[0]
# while i < len(A):
# diff = A[i] - A[i-1]
# if diff != prediff:
# count += (i-head-2)*(i-head-1)/2 #from head to i-1
# head, prediff = i-1, diff
# i += 1
# return count + (i-head-2)*(i-head-1)/2
#dp方法
last = 0
res =0
for i in range(2, len(A)):
if A[i] - A[i-1] == A[i-1] -A[i-2]:
last += 1
else:
last = 0
res += last
return res
446. Arithmetic Slices II - Subsequence
Add to List
Question
Editorial Solution
My Submissions
- Total Accepted: 2425
- Total Submissions:
- Difficulty: Hard
A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequences:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. Asubsequenceslice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0< P1< ... < Pk< N.
A subsequenceslice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.
The function should return the number of arithmetic subsequence slices in the array A.
The input contains N integers. Every integer is in the range of -231and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.
Example:
Input:
[2, 4, 6, 8, 10]
Output:
7
Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
Hide Company Tags
思路：这个题好难想啊！但整体思路是记忆化dp，dp[i][j]表示以第i个数结尾的，差值为j的slice的个数。dp = [{} for _ in A],即dp是一个包含有n个dict的数组，以index i结尾的数可能有不同的diff，用dict记录每个diff。eg：原数组A[1,1,2,3,5,7,8,9]. dp[3]={2:2,1:1},即以第3个数结尾，有2和1两种差值，差值为2的slice有2个，差值为1的有1个。这个时候因为保存的是每两个数之间的差值，不是valid slice，所以不能加到res中去。但是如果我们找到以第j个数结尾的，其中也有差值diff，那就说明i 和之前那个以j结尾的就可以构成一个valid slice了。比如遍历到5，5-3=2，发现在以3结尾的之中也有差值为2的，说明就可以构成slice了，这个时候更新当前计数和res就可以了。
class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
res = 0
dp = [{} for _ in A]
for i in range(len(A)):
for j in range(i):
diff = A[i] - A[j]
dp[i][diff] = dp[i].get(diff, 0) + 1
if diff in dp[j]:
dp[i][diff] += dp[j][diff]
res += dp[j][diff]
return res