給定一列數，如果三個或以上的數滿足等差數列定義，則稱為arithmetic subsequences，問給定的一列數有多少個arithmetic subsequences
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
這題按照思路來說，大概是Medium難度的DP，用python也特別方便好寫，于是閑聊無視非要用C寫了一遍，就真的變Hard模式了，搞了n次才AC，發現果然沒有別人用C來寫。。= =||
總的思路：dp[i][dif]保存處理到第i個數，且相鄰數差值為dif的子數列個數，dp更新：
for i in range(len(nums)):
for j in range(i):
dif = nums[j] - nums[i]
dp[i][dif] += dp[j][dif] + 1
ans += dp[j][dif]
Python很好寫，用dict保存所有可能的dif值就行：
1 #446
2 #Runtime: 2028 ms
3 #Memory Usage: 74.3 MB
4
5 class Solution(object):
6 def numberOfArithmeticSlices(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 dp = [defaultdict(int) for _ in range(len(nums))]
12 ans = 0
13 for i in range(len(nums)):
14 for j in range(i):
15 dif = nums[j] - nums[i]
16 dp[i][dif] += dp[j][dif] + 1
17 ans += dp[j][dif]
18 return ans
C語言版，思路同上，但因為C里面沒有好用的dict，所以用了Hash，LeetCode支持uthash，另外如果直接hash，那么dif的可能性會非常大（cnt保存所有dif的可能性數量），dp數組沒法開那么大，于是，只保存真的形成了3個或以上數字的等差數列的dif值（用cnt2來保存符合這樣條件的dif值的數量），在開dp數組的時候第二維開多大也有一點小trick
交上去的結果：
Runtime: 799 ms, faster than 100.00% of C online submissions for Arithmetic Slices II - Subsequence.
Memory Usage: 240.9 MB, less than 100.00% of C online submissions for Arithmetic Slices II - Subsequence.
Accepted Solutions Runtime Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
Accepted Solutions Memory Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
Invite friends to challenge Arithmetic Slices II - Subsequence
1 //446
2 //Runtime: 799 ms
3 //Memory Usage: 240.9 MB
4
5 struct hashTable {
6 long long key;
7 int val;
8 int init;
9 UT_hash_handle hh;
10 };
11
12 struct hashTable* dict;
13
14 struct hashTable* find(long long k) {
15 struct hashTable* t;
16 HASH_FIND(hh, dict, &k, sizeof(long long), t);
17 return t;
18 }
19
20 int min(int a, int b) {
21 return a<b?a:b;
22 }
23
24 void insert(long long k, int v, int id) {
25 struct hashTable* t = malloc(sizeof(struct hashTable));
26 t->key = k;
27 t->val = v;
28 t->init = id;
29 HASH_ADD(hh, dict, key, sizeof(long long), t);
30 }
31
32 int numberOfArithmeticSlices(int* nums, int numsSize){
33 int ans = 0;
34 int cnt = 0;
35 int idx[numsSize*numsSize];
36 int cnt2 = 0;
37 int dp[numsSize][min(numsSize*numsSize,(int)10000000/numsSize)];
38 memset(dp, 0, sizeof(dp));
39 memset(idx, -1, sizeof(idx));
40 dict = NULL;
41 for(int i = 0; i < numsSize; ++i) {
42 for(int j = 0; j < i; ++j) {
43 long long dif = (long long)nums[j] - (long long)nums[i];
44 struct hashTable* it = find(dif);
45 if(it == NULL) {
46 insert(dif, cnt, i);
47 ++cnt;
48 }
49 else {
50 if(idx[it->val] == -1) {
51 idx[it->val] = cnt2;
52 dp[it->init][cnt2] = 1;
53 dp[i][cnt2] += dp[j][cnt2] + 1;
54 ans += dp[j][cnt2];
55 ++cnt2;
56 }
57 else {
58 dp[i][idx[it->val]] += dp[j][idx[it->val]] + 1;
59 ans += dp[j][idx[it->val]];
60 }
61 }
62
63 }
64 }
65 return ans;
66 }