[数据结构与算法]Leecode1049.最后一块石头的重量-动态规划详细题解及算法思路

Leecode1049.最后一块石头的重量

题目

• 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

  每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
  • 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例：

• 输入：stones = [2,7,4,1,8,1]
  输出：1
  解释：
  组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
  组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
  组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
  组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

详细题解及算法思路

• 为了便于讨论，若最终没有石头剩下，则视作最终剩下了一块重量为 00 的石头。

  例如有四块石头，其重量分别为 aa，bb，cc，dd，且满足 a b c d,a≤b≤c≤d。由于石头的重量不可能增加，无论怎么操作，我们是不可能得到大小为 d+c+b?a 的石头的，该重量已经超过了 c以及 d。

  那么，上述和式的最小非负值所对应的这组 k_i 是合法的吗？

  我们将这组 k_i 对应的石头划分成两堆， k_i =1 的石头分至一堆， k_i =?1 的石头分至另一堆。由于这是最小非负值所对应的 k_i ，这两堆石头重量之差的绝对值也是所有划分当中最小的。

  记这两堆石头重量之差的绝对值为 diff。若能找到一种粉碎方案，使得最后一块石头的重量也为 diff，那就能说明这组 k_i 是合法的。我们不断地粉碎石头。每次粉碎时，记重量最大的石头所处的堆为 AA（若两堆最大重量相同则任选一堆），另一堆为 BB。从 AA 中取出重量最大的石头，BB 中任取一石头，若没有完全粉碎，则将新石头重新放入 AA。这一操作从每堆石头中减去了同样的重量，从而保证重量之差的绝对值在粉碎前后是不变的。若出现一堆没有石头，而另一堆不止一块石头的情况，记有石头的那一堆为 AA，另一堆为 BB。要继续粉碎，则需要从 AA 中取出一块石头移入 BB，然后按规则粉碎。但移入操作让重量之差的绝对值变得更小，与事实（上文加粗文字）矛盾，所以不会出现这种情况。因此，按照上述流程操作，最后一块石头的重量为 diff，所以这组 k_i 对应着一个合法的粉碎结果。

• 就是要凑到二分之一的数组总和

• 动态规划

  • 三大步骤：
    • 确定dp数组的定义：该位置的values[i]+i的值
    • 找出dp数组的递推公式
    • 并且找初始值

Java代码实现

• class Solution {
      public int lastStoneWeightII(int[] stones) {
          int sum = 0;
          for (int weight : stones) {
              sum += weight;
          }
          int n = stones.length, m = sum / 2;
          boolean[][] dp = new boolean[n + 1][m + 1];
          dp[0][0] = true;
          for (int i = 0; i < n; ++i) {
              for (int j = 0; j <= m; ++j) {
                  if (j < stones[i]) {
                      dp[i + 1][j] = dp[i][j];
                  } else {
                      dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                  }
              }
          }
          for (int j = m;; --j) {
              if (dp[n][j]) {
                  return sum - 2 * j;
              }
          }
      }
  }
  

• 由于dp[i+1][] 的每个元素值的计算只和[]dp[i][] 的元素值有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度。对于转移方程
  dp[i+1][j]=dp[i][j]∨dp[i][j?stones[i]]

  在去掉第一个维度后，若仍采用正序遍历，在计算dp[j] 时，dp[j?stones[i]] 的值已经被覆盖，这意味着dp[j?stones[i]] 实际对应的是dp[i+1][j?stones[i]]，即我们计算的是一个错误的转移方程
  dp[i+1][j]=dp[i][j]∨dp[i+1][j?stones[i]]

  若采用倒序遍历，则可消除该错误，这种方式保证计算dp[j] 时，]dp[j?stones[i]] 的值实际对应的是dp[i][j?stones[i]]，从而保证转移方程与去掉维度前一致。

• 优化

  • class Solution {
        public int lastStoneWeightII(int[] stones) {
            int sum = 0;
            for (int weight : stones) {
                sum += weight;
            }
            int m = sum / 2;
            boolean[] dp = new boolean[m + 1];
            dp[0] = true;
            for (int weight : stones) {
                for (int j = m; j >= weight; --j) {
                    dp[j] = dp[j] || dp[j - weight];
                }
            }
            for (int j = m;; --j) {
                if (dp[j]) {
                    return sum - 2 * j;
                }
            }
        }
    }
    

• 如果对波尔数组不太了解也可以使用int 数组

• class Solution {
      public int lastStoneWeightII(int[] stones) {
          int sum=0;
          for(int x:stones)
              sum += x;
          int target = sum / 2;
          int[] dp=new int[target+1];
          for (int i = 0; i < stones.length; i++) {
              for (int j = target; j >=stones[i]; j--) {
                  dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
              }
          }
          return sum-2*dp[target];
      }
  }