这道算法题用「动态规划」求解可麻烦了！

今天药忘吃喽~ 2023-07-13 05:58 13阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

平时我们在解题的时候，如果遇到 `TEL` 的情况，往往我们的第一想法就是使用 **动态规划**，不过今天这道题使用 **动态规划** 貌似不太好使，而需要借助数学里面的一种思路：**正难则反**。

### 题目描述 ###

给你一个整数数组 `target` 。一开始，你有一个数组 `A` ，它的所有元素均为 `1` ，你可以执行以下操作：

*  令 `x` 为你数组里所有元素的和
 *  选择满足 `0 <= i < target.size` 的任意下标 `i` ，并让 `A` 数组里下标为 `i` 处的值为 `x` 。
 *  你可以重复该过程任意次

如果能从 `A` 开始构造出目标数组 `target` ，请你返回 `True` ，否则返回 `False` 。

**示例 1：**

输入：target = [9,3,5]
    输出：true
    解释：从 [1, 1, 1] 开始
    [1, 1, 1], 和为 3 ，选择下标 1
    [1, 3, 1], 和为 5， 选择下标 2
    [1, 3, 5], 和为 9， 选择下标 0
    [9, 3, 5] 完成

**示例 2：**

输入：target = [1,1,1,2]
    输出：false
    解释：不可能从 [1,1,1,1] 出发构造目标数组。

**示例 3：**

输入：target = [8,5]
    输出：true

**提示：**

*  N == target.length
 *  1 <= target.length <= 5 \* 10^4
 *  1 <= target\[i\] <= 10^9

### 题目解析 ###

题目让你用一个元素全为 **1** 的数组构造一个 **target 数组**，规则是每一次操作可以将数组中所有元素的和赋值给其中一个元素，然后反复迭代进行，问你能否构建 **target 数组**。

这道题如果顺着题目想很难得到可行解，你可能会尝试使用暴力的深度优先搜索。

举个例子，你要构建 `[9,3,5]`，起始数组是 `[1,1,1]`，第一次迭代你得到了数组和为 3，那么这个 3 放在数组下标 0,1,2 三个位置都是可行的，你需要每个位置都尝试放一下，这么做是一种解法，但是时间复杂度是指数级别的，对这道题目的输入数据大小来说，不适用。

暴力搜索走不通，你或许会想当然的往动态规划的方向思考，但是这个方向也很难走通，原因在于你很难拆解问题，定义状态。因此这里我们应该换一种思考方式了。

**既然从前往后思考问题得不出答案，那我们就倒着想**。

我们从我们最后想要构建的数组出发（结果），往前推，看能不能推得出全为 1 的初始数组。

怎么推？在回答这个问题之前，我们首先要知道的是，数组元素之间的联系，根据题目描述，我们可以得知数组当前的所有元素和 `sum` 与最大的元素存在着一定的关系，`sum` 是下一次迭代的最大值，那么之前迭代的最大值是否可以根据这个计算出来呢？

**答案是肯定的**，我们来根据例子看看：

[a_max,a_2,a_3,...]
    
    为了简便，我们令 a_other = a_2 + a_3 + ...
    
    sum_prev = a_max              // 之前的 sum 就是当前所有元素的最大值
    sum_cur = a_max + a_other     // 当前的 sum 就是当前所有元素之和
    
    // 因为数组中的元素是在不断改变的，每次只变一个元素
    // 如果要知道之前所有元素的最大值，我们必须还原当前改变的元素
    // 当前改变的元素就是 a_max
    sum_prev = a_prev + a_other = a_max
    a_prev = sum_prev - a_other
           = a_max - (sum_cur - a_max)
           = 2 * a_max - sum_cur

通过上面的一系列推导，我们可以通过当前改变的值（最大值）推得出这个元素在改变之前的值，然后不断地反向推导，就能得出数组里面元素最原始的状态，我们再看是否能得到全为 1 的最原始的数组。

那么这里又存在一个问题，如何动态找出所有元素中的最大值？

这个简单，我们可以借助 **最大堆** 这个数据结构，它可以帮助我们在 `logn` 的时间维护一个排序好的序列。

有了这些，这道题基本上就可以解决了。

以上就是最为基本的解题思路，当然这道题目会存在一些比较极端的 case，比如 `[1, 100000000]` ，因此我们要对之前的解法进行优化。我们之前说过，我们需要考虑 `sum` 还有就是 `max`，但是当 `max` 相对于其他元素过于大的时候，我们需要对这一个元素反复做同样的事情很多次，这个过程能否简化呢？这里我们可以用一个取余的方法做到：

[2, 100]
    
    sum = 102, max = 100, other = 2  
    sum = 100, max = 98, other = 2
    sum = 98, max = 96, other = 2
    ...
    
    // 如果 max 与 other 差距过大，每次迭代我们其实都在更新 max
    // 因为 other 没有变，每次 max 减去的都是相同的值
    // 这里，我们可以利用取余的方式来使得 max 一次性更新到刚好比 other 小的值
    // end_max = max % other

### 参考代码 ###

//author:P.yh
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    
        long sum = 0;
        for (int i : target) {
            pq.offer(i);
            sum += i;
        }
    
        while (pq.peek() != 1) {
            int max = pq.poll();
    
            // 获得 other
            sum -= max;
    
            // other = 1，不管 max 是多少，都可以通过 1 不断迭代而成
            if (sum == 1) {
                return true;
            }
    
            // 由于是反向推，只减不加
            // other 小于 1，说明无法构建
            // other 必须小于 max 来保证 max 的正常迭代递减，不然 max 无法递减到 1
            if (sum <= 0 || max <= sum) {
                return false;
            }
    
            // 通过取余操作将 max 迭代到比 other 小的地方
            max %= sum;
    
            // other + prev_max = prev_sum
            sum += max;
    
            // prev_max 放入队列，继续迭代
            pq.offer(max);
        }
    
        return true;

### 题目总结 ###

取余其实是一个很常用的数学技巧，能够很好地帮助我们节省时间。这道题目有点偏数学了，它的思想其实有点贪心的意思在里面，也就是把局部解衍生到全局。

**通过这道题，其实告诉我们以后思考问题正着想不通，我们完全可以从结果出发，倒着想，说不定有奇效**。

推荐阅读：
    五分钟学算法：动手写一个双向链表
    
    当初我要是这么学习「进程和线程」就好了（附带思维导图）
    
    当初我要是这么学习操作系统就好了（附带思维导图）
    
    啥是布隆过滤器算法？

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9ENjdwZWNlaWJlSVJiTkp1c21LYU5tck9QRTdjeDA3bUF3SWVDd1VmenY4T1RCWElOakNOaWJ6aGJJSGhjaWNmMkI5aWFXUUtEZDdkbjZwaWNPaWNZVVpwWUVwZy82NDA?x-oss-process=image/format,png