贪心算法学习五

例题一

解法（贪⼼）：

贪⼼策略：

我们的任何选择，应该让这个数尽可能快的变成 1 。

对于偶数：只能执⾏除 2 操作，没有什么分析的；

对于奇数：

i. 当 n== 1 的时候，不⽤执⾏任何操作；

ii. 当 n == 3 的时候，变成 1 的最优操作数是 2 ；

iii. 当 (n / 2) % 2 == 0 的时候，那么它的⼆进制表⽰是 ......01 ，最优的⽅式应该选择 -1 ，这样就可以把末尾的 1 ⼲掉，接下来执⾏除法操作，能够更快的变成 1 ；

iv. 当 (n / 2) % 2 == 1 的时候，那么它的⼆进制表⽰是 ......11 ，此时最优的策略应该是 +1 ，这样可以把⼀堆连续的 1 转换成 0 ，更快的变成 1 。

例题二

解法⼀（动态规划）：

将数组按照左端点排序之后，问题就转化成了最⻓上升⼦序列模型，那接下来我们就可以⽤解决最⻓上升⼦序列的经验，来解决这个问题。

1. 状态表⽰：

dp[i] 表⽰：以 i 位置的箱子为结尾的堆起来的箱子序列中，最高的箱子序列的高度；

2. 状态转移⽅程：

dp[i] = max(dp[i] , dp[j] + box[i] ) 其中 0 <= j < i && box[i][0] > box[j][0] && box[i][1] > box[j][1]&& box[i][2] > box[j][2] ；

3. 初始化：

初始化为每个箱子原来的高度；

4. 填表顺序：

从左往右；

5. 返回值：

整个 dp 表中的最⼤值。

例题三

解法⼀（动态规划）：

将数组按照左端点排序之后，问题就转化成了最⻓上升⼦序列模型，那接下来我们就可以⽤解决最⻓上升⼦序列的经验，来解决这个问题（虽然会超时，但是还是要好好写代码）。

1. 状态表⽰：

dp[i] 表⽰：以 i 位置的信封为结尾的所有套娃序列中，最⻓的套娃序列的⻓度；

2. 状态转移⽅程：

dp[i] = max(dp[j] + 1) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] ；

3. 初始化：

全部初始化为 1 ；

4. 填表顺序：

从左往右；

5. 返回值：

整个 dp 表中的最⼤值。

解法⼆（重写排序 + 贪⼼ + ⼆分）：

当我们把整个信封按照「下⾯的规则」排序之后：

i. 左端点不同的时候：按照「左端点从⼩到⼤」排序；

ii. 左端点相同的时候：按照「右端点从⼤到⼩」排序;

我们发现，问题就变成了仅考虑信封的「右端点」，完完全全的变成的「最⻓上升⼦序列」的模型。那么我们就可以⽤「贪⼼ + ⼆分」优化我们的算法。

例题四

解法⼀（动态规划）：

1. 状态表⽰：

dp[0][i]：表示取到第 i 个数的时候%3余数为0的最大值；

dp[1][i]：表示取到第 i 个数的时候%3余数为1的最大值；

dp[2][i]：表示取到第 i 个数的时候%3余数为2的最大值。

2. 状态转移⽅程：

1.当nums[i-1] % 3 == 0时

dp[0][i] = max(dp[0][i - 1], dp[0][i - 1] + nums[i - 1]);
dp[1][i] = max(dp[1][i - 1], dp[1][i - 1] + nums[i - 1])；

dp[2][i] = max(dp[2][i - 1], dp[2][i - 1] + nums[i - 1]);

2.当nums[i - 1] % 3 == 1时

dp[0][i] = max(dp[0][i - 1], dp[2][i - 1] + nums[i - 1]);
dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + nums[i - 1]);
dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + nums[i - 1]);

3.当nums[i - 1] % 3 == 2时

dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + nums[i - 1]);
dp[1][i] = max(dp[1][i - 1], dp[2][i - 1] + nums[i - 1]);
dp[2][i] = max(dp[2][i - 1], dp[0][i - 1] + nums[i - 1]);

3. 初始化：

dp[0][0] = 0, dp[1][0] = INT_MIN, dp[2][0] = INT_MIN;

4. 填表顺序：

从左往右；

5. 返回值：

dp[ 0 ][ n ] 。

解法二（正难则反 + 贪⼼ + 分类讨论）：

正难则反：

我们可以先把所有的数累加在⼀起，然后根据累加和的结果，贪⼼的删除⼀些数。

分类讨论：

设累加和为 sum ，⽤ x 标记 %3 == 1 的数，⽤ y 标记 % 3 == 2 的数。那么根据 sum 的余数，可以分为下⾯三种情况：

a. sum % 3 == 0 ，此时所有元素的和就是满⾜要求的，那么我们⼀个也不⽤删除；

b. sum % 3 == 1 ，此时数组中要么存在⼀个 x ，要么存在两个 y 。因为我们要的是最⼤值，所以应该选择 x 中最⼩的那么数，记为 x1 ，或者是 y 中最⼩以及次⼩的两个数,记为y1,y2 。那么，我们应该选择两种情况下的最⼤值： max(sum - x1, sum - y1 - y2) ；