题解 | #买卖股票的最好时机(四)#

package main

import (
	"fmt"
)

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {
	var n, k int
	_, err := fmt.Scanf("%d %d", &n, &k)
	for err == nil {
		// dp[0] 表示偶数天的状态（覆盖前天的状态）
		// dp[1] 表示奇数天的状态（覆盖前天的状态）
		// dp[day][i][j] 表示剩余i次购买机会，且持有j份股票时，当天所能获得的的最大收益
		// 空间复杂度为O(k)
		var price int
		fmt.Scan(&price)
		var dp [2][][2]int
		dp[0] = make([][2]int, k+1)
		dp[1] = make([][2]int, k+1)
		// 初始化第0天状态，dp[0][i][0]表示不购入股票，收益为0（go初始变量默认为零值，无
		// 需单独设置）
		// （或重复购入然后马上卖出，由于这种无意义操作完全不影响收益，将所有无意义操作移
		// 动至第0天处理，后续不再考虑无意义操作）
		// dp[0][0~k-1][1]表示第0天最后购入股票未卖出，收益为负
		// dp[0][k][1]表示第0天剩余k次购买机会（未消耗购买机会），但却持有股票，为不可能
		// 事件，收益设置为负无穷大
		for i := 0; i < k; i++ {
			dp[0][i][1] = -price
		}
		dp[0][k][1] = -(1 << 31)
		// 时间复杂度度为O(nk)
		for day := 1; day < n; day++ {
			fmt.Scan(&price)
			today := dp[day&1]
			yesterday := dp[day&1^1]
			// 今天剩余0~k-1次购买机会，且持有股票，有2种可能：昨天就持有股票今天无操作，
			// 或昨天未持有股票今天消耗一次购买机会买入
			for i := 0; i < k; i++ {
				today[i][1] = max(yesterday[i][1], yesterday[i+1][0]-price)
			}
			// 今天剩余k次购买机会，但却持有股票，为不可能事件，收益设置为负无穷大
			today[k][1] = -(1 << 31)

			// 今天剩余i次购买机会，且未持有股票，有2种可能：昨天持有股票今天卖出，或昨
			// 天就未持有股票今天无操作
			for i := 0; i <= k; i++ {
				today[i][0] = max(yesterday[i][0], yesterday[i][1]+price)
			}
		}
		fmt.Println(dp[n&1^1][0][0])

		_, err = fmt.Scanf("%d %d", &n, &k)
	}
}

进一步状态压缩：

package main

import (
	"fmt"
)

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {
	var n, k int
	_, err := fmt.Scanf("%d %d", &n, &k)
	for err == nil {
		// dp[i][j] 表示剩余i次购买机会，且持有j份股票时，当天所能获得的的最大收益
		// 空间复杂度为O(k)
		var price int
		fmt.Scan(&price)
		dp := make([][2]int, k+1)
		// 初始化第0天状态，dp[i][0]表示不购入股票，收益为0（go初始变量默认为零值，无
		// 需单独设置，其他语言可能需要设置为0）
		// （或重复购入然后马上卖出，由于这种无意义操作完全不影响收益，将所有无意义操作
		// 移动至第0天处理，后续不再考虑无意义操作）
		// dp[0~k-1][1]表示第0天最后购入股票未卖出，收益为负
		// dp[k][1]表示第0天剩余k次购买机会（未消耗购买机会），但却持有股票，为不可能
		// 事件，无需设置
		for i := 0; i < k; i++ {
			dp[i][1] = -price
		}
		// 时间复杂度度为O(nk)
		for day := 1; day < n; day++ {
			fmt.Scan(&price)

			// 剩余k次购买机会说明一直无操作，收益为0，使用默认零值即可
			for i := 0; i < k; i++ {
				// 今天剩余0~k-1次购买机会，且持有股票，有2种可能：昨天就持有股票今天
				// 无操作，或昨天未持有股票今天买入
				dp[i][1] = max(dp[i][1], dp[i+1][0]-price)
				// 今天剩余0~k-1次购买机会，且未持有股票，有2种可能：昨天持有股票今天
				// 卖出，或昨天就未持有股票今天无操作
				dp[i][0] = max(dp[i][0], dp[i][1]+price)
			}
			// dp[k][0]表示一直无操作，收益为0，使用默认零值即可，其他语言可能需要设置
			// 为0
		}
		fmt.Println(dp[0][0])

		_, err = fmt.Scanf("%d %d", &n, &k)
	}
}

C：

#include <stdio.h>

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}

int dp[101][2];

int main()
{
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        int price;
        scanf("%d", &price);
        for (int i = 0; i < k; i++)
        {
            dp[i][0] = 0;
            dp[i][1] = -price;
        }
        dp[k][0] = 0;
        for (int d = 1; d < n; d++)
        {
            scanf("%d", &price);
            for (int i = 0; i < k; i++)
            {
                dp[i][1] = max(dp[i][1], dp[i + 1][0] - price);
                dp[i][0] = max(dp[i][0], dp[i][1] + price);
            }
        }
        printf("%d\n", dp[0][0]);
    }
    return 0;
}