解題區►Leetcode►Medium

Leetcode 3040 - Maximum Number of Operations With the Same Score II

題目

Problem#

給你一個整數陣列 nums 你可以做三種操作:

  • 刪除開頭兩個數字
  • 刪除結尾兩個數字
  • 刪除頭尾各一個數字

問你最多可以做幾次操作，且每次操作所刪除的數字加起來都要相同

測資限制#

  • $2 \le n \le 2000$
  • $1 \le val \le 1000$

想法#

每次都有三種選擇，因此可以嘗試去搜尋所有狀態

linenums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(int a, int b, int num, int step)
{
    ans = max(ans, step);
    if(a >= b)
        return;

    if(num != -1 && v[a]+v[a+1] == num || num == -1)
    {
        solve(a+2, b, v[a]+v[a+1], step+1);
    }
    if(num != -1 && v[b-1]+v[b] == num || num == -1)
    {
        solve(a, b-2, v[b-1]+v[b], step+1);
    }
    if(num != -1 && v[a]+v[b] == num || num == -1)
    {
        solve(a+1, b-1, v[a]+v[b], step+1);
    }
}

但這樣會 TLE，經過觀察(或 print)，可以發現 a 和 b 存在子問題重疊的關係(舉例如下)，因此如果可以改寫以上解法成 top down DP 就可以將複雜度降低

1
2
3
4
5
6
7
delete 0 1
delete 5 6
=> solve(2, 4)

delete 0 6
delete 1 5
=> solve(2, 4)

AC Code#

  • 時間複雜度: $\mathcal{O}(n^2)$
  • 空間複雜度: $\mathcal{O}(n^2)$

心得#

賽中差一點寫出來QQ 差 memorization