问题描述

1. John 有两个孩子，在 John病逝后，留下了一组价值不一定相同的魔卡， 现在要求你设计一种策略，帮John的经管人将John的这些遗产分给他的两个孩子，使得他们获得的遗产差异最小（每张魔卡不能分拆）。

2. 假设已知某股票连续若干天的股价，并且如何时候你手上只能由一支股票，即如果你要买入就得先将手上股票卖出，设计一个算法来计算你所能获取的最大利润。你最多可以完成 k笔交易。也就是说，你最多可以买k 次，卖 k 次。

   输入：k = 2, prices = [3,2,7,5,1,4]
   输出：8
   
   7-2  +  4-1
   

解题思路

T1

这是一个经典的贪心算法问题：

1. 将所有的魔卡按照价值从大到小排序。
2. 从价值最高的魔卡开始，依次分配给两个孩子中当前遗产较少的那个孩子。
3. 重复步骤2直到所有的魔卡都被分配完毕。

这种贪心分东西的思路非常常见，一眼望穿

类似的题目还有捡大小垃圾放两个垃圾袋呀等等。

T2

那么这道题到底是贪心还是动规呢？

我们知道动规有一道经典例题，就是非升子序列，不觉得这题有几分相似，都是必须从前往后求最优。其实要证明贪心算法不行只要举个反例就行了。

于是就根据经验按照动规的思路来思考。考虑使用二维数组dp[i][j]，代表当前状态的最大利润，i代表当前是第i次买卖，j代表当前是第j天。

对于每个状态都有买和不买。为什么是买和不买呢，不是还有卖吗？其实是赚钱和不赚钱这两种选择，赚钱是卖与买之间的差值。所以这道题比一般的动态规划要更复杂些。

对于每一次买卖，必须有买才有卖，先用maxDiff包括因为买股票亏的钱，一开始由于没有股票，就等于-prices[1]。这个亏的钱也完全不是负数亏的钱，还要包括之前(上一次买卖)因为赚钱累计的成本，这个maxDiff就是代表本次买卖状态下的累计成本(比较难理解)。所以$$maxDiff=max(maxDiff,dp[i-1][j]-prices[j])$$

对于每一天，都有去赚钱和不赚钱。不赚钱利润等于昨天的利润，去赚钱的利润等于累计成本maxDiff加上prices[j]，因此$$dp[i][j]=max(dp[i][j-1],prices[j]+maxDiff)$$

在样例下，dp运算结果如下所示。

prices	3	2	7	5	1	4
dp[1][j]	0	0	5	5	5	5
dp[2][j]	0	0	5	5	5	8

这个dp[k][n]就是answer。

完整代码

T1

#include <iostream>
#include <algorithm>

using namespace std;

// 分配遗产的函数
void distributeInheritance(int cards[], int n) {
    // 排序魔卡
    sort(cards, cards + n, greater<int>());

    // 初始化两个孩子的遗产值
    int child1_inheritance = 0;
    int child2_inheritance = 0;

    // 分配遗产
    for (int i = 0; i < n; ++i) {
        if (child1_inheritance <= child2_inheritance) {
            child1_inheritance += cards[i];
        } else {
            child2_inheritance += cards[i];
        }
    }

    // 输出两个孩子的遗产差异
    cout << "遗产差异最小为：" << abs(child1_inheritance - child2_inheritance) << endl;
}

int main() {
    // 输入魔卡数量
    int n;
    cout << "请输入魔卡数量：";
    cin >> n;

    // 输入每张魔卡的价值
    int cards[n];
    cout << "请输入每张魔卡的价值：" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> cards[i];
    }

    // 调用分配遗产函数
    distributeInheritance(cards, n);

    return 0;
}

/* sample input
8 
2 5 6 7 1 7 4 3
*/

输出结果

请输入魔卡数量：8
请输入每张魔卡的价值：
2 5 6 7 1 7 4 3
遗产差异最小为：1

T2

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k,prices[100],dp[101][101]; // 动态规划数组大小修改为dp[101][101]
    cin>>n>>k;
    memset(dp,0,sizeof(dp));
    memset(prices,0,sizeof(prices));
    for(int i=1;i<=n;i++)
        cin>>prices[i];
    for(int i=1;i<=k;i++){
        int maxDiff = -prices[1]; // 数组prices的下标从1开始
        for(int j=1;j<=n;j++){ 
            dp[i][j] = max(dp[i][j-1],prices[j] + maxDiff);
            maxDiff = max(maxDiff, dp[i-1][j] - prices[j]);
        }
    }
    cout<<dp[k][n]<<endl;

    // 打印dp数组
    cout<<"|dp|";
    for(int i=1;i<=n;i++)
        cout<<i<<"|";
    cout<<endl;
    cout<<"|";
    for(int i=1;i<=n+1;i++)
        cout<<"-|";
    cout<<endl;
    for(int i=1;i<=k;i++){
        cout<<"|"<<i<<"|";
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<"|";
        cout<<"\n";
    }
    return 0;
}

/* simple input
6 2
3 2 7 5 1 4
*/

输出结果

6 2
3 2 7 5 1 4
8
|dp|1|2|3|4|5|6|
|-|-|-|-|-|-|-|
|1|0|0|5|5|5|5|
|2|0|0|5|5|5|8|