算法竞赛: 动态规划引入

Posted on 2024-03-11 Edited on 2025-12-31 In Algorithm , DP Word count in article: 6.9k Reading time ≈ 25 mins.

回溯与动态规划与贪心引入

概念

回溯法可用于求解绝大多数问题，基于深度优先，但并不是很优秀的方法，遵循自顶而下，通常通过递归实现
动态规划也可用于求解许多问题，从最小边界求出上层解，遵循自底而上，达到一定规模后则得到答案，但也需要更多思考
贪心思想总在追求局部最优解，由多个局部最优叠加得到全局最优

求解斐波那契数列

边界条件为a[0] = a[1] = 1

从回溯法的角度思考，将大问题拆解为子问题，只有深挖到边界条件时才回溯

int fibonacci(unsigned int _position) {
    if (!_position || _position == 1) {
        return 1;
    }
    return fibonacci(_position - 1) + fibonacci(_position - 2);
}

一般的回溯法必然涉及大量重复的运算，优化方法只有剪枝，即可以编写函数优化判断条件及时回溯，或用数组存储已经求出的记录：

int fibonacci(unsigned int _position) {
 static int hash[__INT_MAX__] {1, 1}; // 变长数组不能拥有静态存储期.
    if (hash[_position - 1]) {
        return hash[_position - 1];
    }
    else {
        hash[_position - 1] = fibonacci(_position - 1) + fibonacci(_position - 2);
    }
    return hash[_position - 1];
}

这已经有动态规划的影子了，只不过从概念上，动态规划是从a[0, 1]开始找答案：

int fibonacci(unsigned int _position) {
    int dp[_position] {1, 1};
    for (int i = 1; i != _position - 1; i++) {
        dp[i + 1] = dp[i] + dp[i - 1];
    }
    return dp[_position - 1];
}

显而易见修改为循环形式的求解能利用变长数组，节省了许多空间，这里称dp[0,\ 1]为base case，即边界条件，dp[i + 1] = dp[i] + dp[i - 1]为状态转移方程，即从上一个已求解的子问题状态转移到当前问题状态的方程

根据状态转移方程的不同可以实现对空间的优化，例如这个问题的方程，事实上只需要维护三个数，通过滚动数组，将过于小的问题抛弃：

int fibonacci(unsigned int _position) {
    int dp[3] {1, 1}; // 虽然用数组, 但是三个变量就可以完成记录.
    for (int i = 1; i != _position - 1; i++) {
        dp[(i + 1) % 3] = dp[i % 3] + dp[(i - 1) % 3];
    }
    return dp[(_position - 1) % 3];
}

拆解斐波那契数列

问题描述：任意一个正整数可以拆解为若干个斐波那契数列的数(可以重复)之和，求出子数个数最小的拆法

这是一个完全背包问题，即一个容量固定的背包，需要用一些重量不同，数量无穷的物品刚好填满它，求出使用物品最少的方案

如果使用贪心，即我需要更少的数，就选择更大的数，即时刻让接下来需要计算的数更小，这实际上有一个问题：如果拆解出的小问题恰好不大不小，反而增加了需要用到的数，结果就是错误的

求最大连续子数组和

这种问题要求连续选择，反而用贪心思想和搜索更优：

明确贪心：如果当前和小于零，则抛弃当前窗口，否则继续；如果新窗口和大于旧最大值，则更新答案窗口

// 保证数组不为空.
array max_son(vector<int>& arr) {
 int sum = arr[0], max=sum;
    auto itbegin=arr.begin(), itend=pbegin; // 存储答案的两个迭代器.
    auto itslow=itbegin, itfast=itslow; // 当前窗口的两个迭代器.
    while (itfast != arr.end()) {
        if (sum < 0) {
            itfast++;
            itslow=itfast;
            if (itfast != arr.end())
             sum=*itfast;
            else
                break;
        }
        if (sum > max) {
            itbegin=itslow;
            itend=itfast;
            max=sum;
        }
        itfast++;
    }
    return array(itbegin, itend);
}

动态规划

基本思路

动态规划在贪心的基础上做出的优化在于，这种算法能看到更长远的子问题(因为本身就是从子问题上升求解的)，如果用f(x)表示对一个问题的最优解，那么dp在子问题中挑出最优解better[f(x1), f(x2), f(x3)]，最终访问到最基础的最优解，也就得到了全局的最优解

例如用1, 5, 6分凑10分的情况，贪心会选择6+1+1+1+1，而动态规划选择better[f(10-6)+1, f(10-5)+1, f(10-1)+1]，即在全局上贪心

所以对于能用dp解决的问题：

拥有最优子结构：即大问题可拆分成子问题，而且子问题有唯一的最优解
能够确定初始状态，即base case
能够求出状态转移方程，即递推公式，这是拆分的基础

也就是，我在做决策时，只需要考虑当前状态了，因为子问题已经是最优了

判断可以用动态规划后，可一步步思考解法：

明确dp的维度及含义
列出所有状态
考虑不同状态，取最优解，列出状态转移方程
思考base case与如何初始化数组
dp维度的遍历顺序
测试时输出整个dp数组，方便寻找问题所在

基础背包问题

01背包

给定一个容量固定的背包，将一些物品放入其中，其中每种物品只有一件，求出最大价值方案/不同价值方案数/最少物品数

每种物品只有选/不选两种状态，这称为01，以求出最大价值方案为例：

dp[i][j]：表示用前i种物品填满容量为j的背包，所得到的最大价值
状态转移：dp[i][j]=max(dp[i-1][j], dp[i-1][j-weights[i]]+value[i])。max中前者为不选择第i种物品，则与使用前i-1种物品相同；后者为选择第i种物品，则当前价值为用前i-1种物品填满”当前容量减去当前物品的重量”背包的最大价值加上当前物品的价值。两者取最优，在这里表现为max()；为防止越界访问，定义当当前物品重量大于当前背包时，必定为不选择当前物品
base case：dp[...][0]=0，即容量为0，价值定为0；dp[0][weights[0]~k]=value[0]，即用第0种物品填满容量为weights[0]~k的背包，最大价值就是当前物品的价值。注意这里不要求恰好填满，如果要求恰好，则有所不同
这个问题不要求顺序，因为根据递推方程，当前元素由左上或正上方元素决定；根据base case，第0行与第0列都已经初始化；故顺序不同都可以在求当前位置前求出这两个位置的值

状态转移方程中，由于每种物品只有一件，所以每次迭代都需要i-1，避免重复选择：

#include <vector>
// 这里进行简化, 用 value下标+1 表示该物品的重量.
int max_value(const vector<int>& value, int k) {
    int dp[value.size()][k+1] {};
    for (int i = 1; i < k+1; i++) { // i的初始化为weights[i].
        dp[0][i]=value[0]; // 该问题不要求恰好填满, 所以初始化一个范围.
    }
    for (int i = 1; i < value.size(); i++) {
        for (int j = 1; j < k + 1; j++) {
            if (i+1 > j) { // 这里的i+1是简化后的重量, 具体问题中应为weights[i].
                dp[i][j]=dp[i-1][j];
                continue;
            }
            dp[i][j]=max(dp[i-1][j], dp[i-1][j-(i+1)] + value[i]);
        }
    }
    return dp[value.size()-1][k];
}

观察递推方程可知，当前元素只与左上/正上方元素相关，则可以利用滚动数组优化空间：

#include <vector>
int max_value(const vector<int>& value, int k) {
    int dp[k+1] {}; // 将物品维度压缩.
    for (int i = 1; i < k+1; i++) {
        dp[0][i]=value[0];
    }
    for (int i = 1; i < value.size(); i++) { // 倒序遍历一定需要整一层的初始化.
        for (int j = k; j > 0; j--) {
            if (i+1 > j) {
    continue; // 直接用正上方的数据覆盖, 则不作改变.
            }
            dp[j]=max(dp[j], dp[j-(i+1)] + value[i]);
        }
    }
    return dp[k];
}

注意这样优化必然需要让背包容量在内层循环，因为是行行覆盖；而且背包是倒序遍历，因为需要保证在每一层的计算中(i不变时)，每个物品只被选择一次；如果正序遍历，会因”由前一元素推出当前元素”的影响，错误的用新值覆盖本应用于计算的旧值

完全背包

完全背包与01背包的不同在于，每个物品有无数个，这使它们有多种状态(选0,1,...,n次)，最多选择”背包容量除以重量”次；这样的问题可以转换为01背包(将每种物品按最多次数展开就是01背包)：

如果不选择，则等于上层结果
如果选择若干次后不再选择，则等于该层结果
如果继续选择，则覆盖该层结果

则很容易想到新增一层循环，达成”选择多次”：

int max_value(const vector<int>& value, int k) {
    int dp[value.size()][k+1] {};
 for (int i = 1; i * 1 < k+1, i += 1) { // 后两个表达式中的1是简化后的第0物品的重量.
        for (int j = i * 1; j < i * 2 && j < k+1; j++) {
         dp[0][j]=i * value[0]; // 不要求填满.
        }
    }
    for (int i = 1; i < value.size(); i++) {
        for (int j = 1; j < k + 1; j++) {
            dp[i][j]=dp[i-1][j]; // 先进行初始化, 方便多次比较.
            for (int x = 1; x * (i+1) <= j; x++) { // 最多选择 容量/单个重量 次.
                dp[i][j]=max(dp[i][j], dp[i-1][j-x * (i+1)] + x * value[i]);
            }
        }
    }
    return dp[value.size()-1][k];
}

注意到每次算出一个dp[i][j]，其实是对该元素正上方元素、正上方左边若干个元素(两两之间距离为weights[i])进行比较(只是因为max一次性只比较两个元素而遍历)，且每一层循环所要判断的物品是同一种(重量一样，选择不同个数物品后元素的距离一样)，那么只需要利用上一次比较的结果(即当前元素正上方左边元素的最优)与当前元素正上方元素相比较，就可以减少不必要的比较了，于是可以对状态转移方程优化：

int max_value(const vector<int>& value, int k) {
    int dp[value.size()][k+1] {};
 for (int i = 1; i * 1 < k+1, i += 1) {
        for (int j = i * 1; j < i * 2 && j < k+1; j++) {
         dp[0][j]=i * value[0];
        }
    }
    for (int i = 1; i < value.size(); i++) {
        for (int j = 1; j < k + 1; j++) {
            if (j-(i+1) < 0) {
                dp[i][j]=dp[i-1][j];
                continue;
            }
            // max前者为正上方元素, 后者为之前计算过的最优解+多选择一件的价值.
            dp[i][j]=max(dp[i-1][j], dp[i][j-(i+1)]+value[i]);
        }
    }
    return dp[value.size()-1][k];
}

不难发现这个方程与01背包极为类似，只因后者变化而允许了重复选择

效仿01背包，依然可以降维：

int max_value(const vector<int>& value, int k) {
    int dp[k+1] {};
 for (int i = 1; i * 1 < k+1, i += 1) {
        for (int j = i * 1; j < i * 2 && j < k+1; j++) {
         dp[j]=i * value[0];
        }
    }
    for (int i = 1; i < value.size(); i++) {
        for (int j = 1; j < k + 1; j++) { // 这里是正序, 因为可以选择多次.
            if (i+1 > j) {
    continue;
            }
            dp[j]=max(dp[j], dp[j-(i+1)] + value[i]);
        }
    }
    return dp[k];
}

完全背包可以考虑的一个优化点在于，对于求解价值问题，可以考虑将”重量相同但价值更小”与”价值相同但重量更大”的物品去除，因为可以选择无数次，而这样的优化首先需要O(n²)的遍历，或者用一些高效的排序方法实现更低的复杂度优化

多重背包与混合背包

多重背包与完全背包十分相似，它限定了物品的个数。最基础的解法为类似完全背包的三次循环，为了防止多次选择，一维数组解法的j层循环仍需逆序遍历

因为这种解法实质上是通过完全展开所有的次数来表示所有的可能，也就是用1进制形式重构了物品，会造成多余无效的比较，所以：

将这些1进制的多个同种物品压缩成n进制不同种的01物品，价值为n*value[i]，重量为n*weights[i]，个数为1
尝试找出一种压缩方法，能使压缩后的这些物品进行排列组合后能够表示所有的可能
因为01物品只有两种状态选或不选，所以只能用二进制压缩

完全背包问题可以完全优化掉个数的循环，而多重背包不行：

void init_input(vector<vector<int>>& input) { // 初始化输入.
    int n, m, v, w;  // 物品种类数, 物品个数, 物品价值, 物品重量.
    cin >> n;
    for (int i = 0, j; i < n; i++) {
        cin >> m >> v >> w;
        j = 1;
        while (j <= m) {
            input.push_back(vector<int>(v*j, w*j));
            m -= j;
            j <<= 1;
        }
        if (m) { // 如果剩余m个, 则把它压缩为1个, 加上这个余数就可以表示原来的m范围内所有数了.
            input.push_back(vector<int>(v*m, w*m));
        }
    }
}

这样在遍历时套用01背包解法就行了，对于个数的时间复杂度由O(n)优化成了O(logN)，乘上价值与重量的时间复杂度的话，已经优化相当多了

混合背包即将三种物品类型结合起来，很容易得出它的解法：

如果是完全背包类型，则这一层以完全背包方程遍历，一维数组是顺序遍历
如果为多重背包类型，则转化为01背包，并加入到01背包的循环中，一维数组是倒序遍历

变种背包问题

以上是三种最基础、经典的背包问题，也有不同的变式，例如：

外表上只含重量的背包问题：例如数组凑出固定和问题，在这个问题上，价值其实与重量相等
输出具体方案：可以同时维护一个bool二维数组记录选择。例如01背包中，用0表示没有选择，并查询正上方的选择；用1表示选择了，并查询[i-1][j-weights[i]]的状态；最后通过递归逆序搜索，顺序输出即可
作”恰好装满”的限制：初始化时必须注意有效状态(装满为有效，否则定义为-1或其它无效值)，在求最大价值问题上，应用INF或__INT_MAX__作为无效值(因为取最大)
求解最少物品恰好装满问题：dp数组含义变为所需的最少物品，且初始化时无关值应用__INT_MAX__处理，在比较时使用min()，无效值为-1；之前提到的拆分斐波那契数列问题其实就是一个这样的完全背包问题
求解恰好填满方案数问题：dp数组含义变为方案数，且递推方程由比较变为两种状态求和，无效值为-1

求解价值最优方案数问题：同时维护一个二维数组记录最优方案数。如果选择/不选择价值相等，则当前方案数为两者相加，否则为更优方案的方案数，以01背包为例：

int strategy[value.size()][k+1] {};
for (...) {
    for (...) { // 二维数组求法.
        ...; // 递推公式.
        if (dp[i][j] == dp[i-1][j])
            strategy[i][j] += strategy[i-1][j];
        if (dp[i][j] == dp[i-1][j-w[i]]+value[i])
            strategy[i][j] += strategy[i-1][j-w[i]];
    }
    for (...) { // 一维数组求法.
        if (dp[j] > dp[j-w[i]]+value[i]) {
            strategy[j] += strategy[j];
        }
        else if (dp[j] < dp[j-w[i]]+value[i]) {
            strategy[j] += strategy[j-w[i]];
            dp[j] = strategy[j-w[i]];
        }
        else {
            strategy[j] += strategy[j-w[i]]+strategy[j];
        }
    }
}

求解排列顺序问题：和求解组合数不同，对于完全/多重背包时，因为一种物品可以多次选择，于是有顺序问题，所以求解所有排列时，如果只使用两层循环，需要让外层循环为背包容量，内层循环为物品
- 原因在于，求组合时，是先往背包中放同一种物品，然后遍历后续的物品，始终只有一种排列
- 而求排列时，允许背包先放入不同的物品，然后再扩大容量
- 可以这么认为，前者一次遍历只允许出现一种物品，后者一次遍历则是求出了小背包的所有组合
连续选择问题：即要求选择的物品必须是连续的，这种方法难以通过dp求解，更好的办法是通过贪心与搜索

对于背包问题，不用纠结它有没有背包，背包只是一系列问题的一种映射，重要的是”只需要作出当前决策”的特性

进阶背包问题

二维背包问题

这类问题在基础背包问题上添加了一个限制，例如：

两个背包问题：放入一个物品会使这两个背包都添加重量
数量限制问题：可以放入背包的物品最大数量有限(假设为k)，这个”最大数量”其实就是第二个容量为k的背包，放入物品同时会使它的重量加1

按照之前的思路，只需要添加一层循环与一个维度即可，利用滚动数组可以只使用二维数组

分组背包问题

这类问题将n种物品改为n组物品，且在每组中只能选出1件，那就是很简单的嵌套最优01背包问题，只需要添加一层循环，但不需要添加数组维度：

for (int i = 1; i < group.size(); i++) {
    for (int j = k; j > 0; j--) {
        for (int x = 0; x < group[i].size(); x++) {
            if (i+1 > j) { // group[i].weights[x] > j.
                continue;
            }
            dp[j]=max(dp[j], dp[j-(i+1)] + group[i].value[x]);
        }
    }
}

这是依赖问题的基础，此问题的变形还有：

每组不限种类，总共能选择n件，这其实是二维背包问题，淡化了”组”的分别
每组只能选出1种，且能够选择多/无数件，这也很好解决，套用多重/完全背包模板再添加循环即可
每组能够选出n种，每种能够选择1/多/无数件，这样的问题已经变得相当复杂，涉及不同排列组合问题

依赖背包问题与泛化物品

这是进阶背包问题，每种物品可能与其它物品有依赖关系，即选择附属物品必须选择对应的主物品，这使得附属物品有有效状态和无效状态之分，而不单纯是有效状态上选择或不选择的区别

遍历思路一定是如果选择主物品，再考虑其附属物品，所以首先考虑缩小附属物品的范围，即先在每一个主物品的附属集合中使用背包策略求出子dp，再与不选主物品的情况捆绑成一个组，由于每个元素代表一种策略，而我们只能选择一种策略，故可以通过分组背包问题求解

如果一组附属物品只依赖于一个主物品，那么产生的组就是子dp(每个元素需加上主物品的重量与价值，因为有依赖关系)，不选择主物品的情况就是不在这个组里选择任何物品

泛化物品概念的来源是，假设这些附属物品也有附属物品，那么问题就变成了背包数，是一个图了

根据依赖问题的思路，将附属物品的集合看作一种新的物品，这种物品可以是一个组，表现为一个dp数组，即提供不同的容量限制，它会返回不同的价值，这就是泛化物品

泛化物品当然可以作为三个基础背包问题的对象，而一旦容量与类型确定，它的价值也都固定了：

01泛化物品：提供容量k，选择则weight=k, value=dp[k]
多重或完全泛化物品：提供容量k，选择则weight=w[i], value=k/w[i] * dp[w[i]]

取泛化物品中的最优是有点麻烦的，因为它们的容量不确定，暴力解决是枚举所有分配容量的方案，再取最优

例题

目标和

给你一个没有0的数组，每个数可以取正或负，得到一个表达式，再给你一个正的目标和，求出能够得到这个目标和的表达式数

这也是很经典的01背包问题，求恰好填满，只是状态从是否选择变成了是否取正负且每个数必须选择，事实上这样会不能进行一维数组的空间优化：

int solution(vector<int>& arr, int target) {
    for (...) {...}; // 求出fabs(arr)的和sum.
    if (target > sum) {
        return 0;
    }
    int dp[sum+1] {};
    dp[0] = 0; // 数组没有0, 故可以确定用第一个数凑出0的方案数为0. 如果允许不选, 应为dp[0]=1.
    dp[fabs(arr[0])]=1;
    for (int i = 1; i != arr.size(); i++) {
        for (int j = sum; j > 0; j--) {
            if (arr[i]+j > sum && arr[i] > j) { // 既不能取正也不能取负.
                dp[j] = 0; // 如果允许不选, 这里应该不变.
            }
            else if (arr[i] > j) { // 如果只能取正.
                dp[j] = dp[arr[i] + j]; // 允许不选, 则+=.
            }
            else if (arr[i]+j > sum) { // 如果只能取负.
                dp[j] = dp[j-arr[i]];
            }
            else { // 都可取.
                dp[j] = dp[arr[i] + j] + dp[j-arr[i]];
            }
        }
    }
    return dp[target];
}

很明显，dp同时受到左右两边元素的影响，是不能用一维数组的

求解最后一块石头的重量

给你一些石头，石头之间可以互相抵消，求出抵消剩一块石头时，这块石头的最小重量

如果要求两块石头相邻，很容易用贪心思想得到，每轮抵消我都要让最大的石头和旁边的石头抵消(无关左右)，每轮抵消后再次寻找最大的石头，因为虽然最大值可能互相隔离，但最终都要相碰，最后三个石头的抵消实际上是在做：

新大石头-(旧大石头-隔壁石头)=新大石头-旧大石头+隔壁石头

它一定是两个小石头的和减去那个大石头

那如果不要求相邻，根据上面的思路就是抽出一些石头取正数，一些石头取负数，然后求最小和，那么在求出dp后，从小遍历最后一行就能得到答案了

分割字符串

给你一个字符串和字典，你可以重复使用字典中的字符串，求解是否能够通过字典来凑出它

示例：str="applepenapple", dict=["apple", "pen"]，返回true

这就是一个完全背包问题，字符串的容量为size()，字典中每个物品的重量也为size()，只需要求出所有能够恰好凑出容量的排列即可，注意需要保存具体的组合内容

然而求出所有排列是深搜的做法，dp可以在此之前就进行判断，剔除无关的字符串，判断条件可以是集合的count()方法，并充分利用前面的状态，这样就可以将排列数转换为布尔值了

bool isdict(const string& str, const unordered_set<string>& dict) {
    bool dp[str.size()+1];
    dp[0] = 1; // 表示可以凑出空字符串, 方便记录第一个出现的字典串的状态.
    for (int i = 1; i < str.size() + 1; i++) { // 先遍历背包容量, 即子串.
        for (int j = 0; j < i; j++) { // 遍历子串的子串.
            // 将0~i子串拆分为0~j和j~i两个子串, dp[j]表示可以凑成0~j, 后者表示字典含有j~i串.
            if (dp[j] && dict.count(str.substr(j, i-j))) {
                dp[i] = 1; // 则可以凑成0~i.
                break;  // 增加背包容量.
            }
        }
    }
    return dp[str.size()];
}

打家劫舍系列问题

打家劫舍一：给你一行屋子，你可以抢劫非相邻房屋，求出最大收益

这个问题，不同物品间有排斥关系，而且看似没有背包，很简单：

int max_p(const vector<int>& arr) {
    if (arr.size() == 1) {
        return arr[0];
    }
    int dp[arr.size()] {}; // 这里用dp[i]表示抢劫前i间屋所得的最大收益.
    // 初始化: 0比1大或相等, 则抢0不抢1, 表现为[0]==[1]; 0比1小, 则抢1不抢0, 表现为[0]!=[1].
    dp[0]=arr[0];
    dp[1]=max(dp[0], arr[1]);
    for (int i = 2; i < arr.size(); i++) {
        if (dp[i-1] == dp[i-2]) { // 证明没有抢前者, 则假设抢当前屋, 不抢的情况在下一轮处理.
            dp[i]=dp[i-1]+arr[i];
        }
        else { // 证明当前屋不可抢.
            if (arr[i] + dp[i-2] > dp[i-1]) { // 但如果抢i比抢i-1划算.
    dp[i-1]=dp[i-2]; // 则修改前一个元素的状态.
                dp[i]=dp[i-2] + arr[i];
            }
            else { // 不抢.
                dp[i]=dp[i-1];
            }
        }
    }
    return dp[arr.size()-1];
}

打家劫舍二：仍然给你一些屋子，但这个屋子头尾相邻，你不能抢劫相邻的屋子

这其实分成三种情况：

头尾都不选：答案等于对中间元素进行dp
只选头：答案等于对前n-1个元素进行dp
只选尾：答案等于对后n-1个元素进行dp

第一种情况是被包含在后两种情况中的，也就是求的过程中就已经取了最优，而后两种情况只需要分别计算再取最优即可

打家劫舍三：给你一些树状结构的房子，依然是不能抢劫相邻的屋子

一节二叉树可以化为普通的线性数组，但多节多叉树就要考虑多种因素，那么其实这涉及到树形dp

处理树形结构一个可行的方法就是递归搜索，并同时运用dp

贪心之多背包问题

给你k个背包，n个珠子(n>=k)，你必须把所有珠子填入其中且保证每个背包含有至少1个珠子，且每个背包内珠子一定是连续放入的，每个背包的价值为最先放入珠子和最后放入珠子的和，求出所有背包价值和最大值与最小值的差值

这个问题中各个背包之间的关系其实不大，很难用动态规划来求解，而是用贪心思想

任意方案都要求将整个数组分割成k个连续子数组，以代数形式列出价值和：

$\begin{align}&\rm\because arr[0,n]=arr[0,n_1],arr[n_1+1,n_2],\dots,arr[n_{k-1}+1,n]\\&\rm\therefore sum=value\Big(0+n_1+(n_1+1)+n_2+\dots+(n_{k-1}+1)+n\Big)\\&\ \ \ \ \ \ \ \ \ \ \ \ =\rm value\Big(0+\big(n_1+(n_1+1)\big)+n_2+\dots+(n_{k-1}+1)+n\Big)\end{align}$

由观察可知，一个方案的价值总和等于头尾元素价值之和+所有分割处相邻元素价值之和，且共有k-1个分割处

我们知道n的数组有n-1个分割处，那么只要把所有这些分割处两边元素和求出，再由贪心取最大/最小的k-1个分割处，就可以算出最大/最小值了：

int sub(vector<int>& arr, int k) {
    int sum = 0;
 for (auto it = arr.begin(); it != arr.end()-1; it++) {
        *it += *(it+1); // 数组内计算, 节省空间.
    }
    // 排序, 方便贪心, 这里因为数组内计算, 所以最后一个元素是无效的.
    sort(arr.begin(), arr.end()-1);
    for (int i = 0; i < k-1; i++) { // 遍历k-1次.
        sum += arr[arr.size()-2-i] - arr[i]; // 求的是差值.
    }
    return sum;
}