1049. 最后一块石头的重量 II

发表于 分类于 阅读次数： Waline： 本文字数： 250 阅读时长 ≈ 1 分钟

考点

  • 01背包

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  static const int maxn = 35, maxm = 3e3 + 50;
  int n, m;
  bool f[maxn][maxm];
  int lastStoneWeightII(vector<int>& stones) {
    n = stones.size(), m = 0;
    for (int i = 0; i < n; ++i) m += stones[i];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= m; ++j) {
        if (!f[i][j]) continue;
        f[i + 1][j + stones[i]] = 1;
        f[i + 1][abs(j - stones[i])] = 1;
      }
    }
    for (int j = 0; j <= m; ++j) {
      if (f[n][j]) {
        return j;
      }
    }
    return 0;
  }
};

思路

贪心不行，比如{1, 1, 2, 4}，先让两个1消除那么最后会得到2，应该前两个1攒着，加上2，再减去4，得到0

由此得到启发，设转移方程如下：

1
2
3
4
5
f[i][j]: 前i个石头, 凑成j的可行性
Push方向, 即已知f[i], 推f[i+1]
如果当前f[i][j]是可行的, 对于stones[i+1]有两种办法:
不跟它合并, 攒着, 那么转移到f[i+1][j + stones[i+1]]
跟它合并, 转移到差的绝对值即可f[i+1][abs(j - stones[i])]