记录---股票买卖问题（动态规划）

import java.util.Scanner;
/** * 股票买卖，int K为最大交易次数，int[] prices为股票价格，prices[i-1]表示第i天的股票价格 * 求收益最大化时的收益 * */
public class DP7 {
   
    public static void main(String[] args) {
   
        //int k = 3;
        //int[] prices = {1,3,4,1,9,5,11,99};
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        int k = Integer.valueOf(s1);
        String s2 = sc.nextLine();
        String[] str = s2.split(" ");
        int[] prices = new int[str.length];
        for (int i = 0; i < str.length ; i++) {
   
            prices[i]=Integer.valueOf(str[i]);
        }

        DP7 dp7 = new DP7();
        int res = dp7.dp(k, prices);
        System.out.println(res);
    }

    int dp(int K,int[] prices){
   
        int N = prices.length;
        int[][][] dp = new int[N+1][K+1][2];
        //base case
        for (int i = 0; i <K+1 ; i++) {
   
            //还没开始，利润为0
            dp[0][i][0]=0;
            //还没开始，不可能持有股票，用负无穷表示不可能
            dp[0][i][1]=(int)Float.NEGATIVE_INFINITY;
        }
        for (int i = 0; i <N+1 ; i++) {
   
            //k为0表示不允许交易,利润为0
            dp[i][0][0]=0;
            //k为0表示不允许交易，不允许交易的情况下是不可能持有股票的，用负无穷表示不可能
            dp[i][0][1]=(int)Float.NEGATIVE_INFINITY;
        }
        for (int i = 1; i <N+1 ; i++) {
   
            for (int j = 1; j <K+1 ; j++) {
   
                //当前未持有股票，有两种可能
                //昨天就没有持有，今天选择观望，收益为到昨天的收益dp[i-1][j][0]
                //昨天持有股票，今天卖了，收益为到昨天持有股票的收益加今天卖出去的收益dp[i-1][j][1]+prices[i-1]
                //两者取较大的收益作为今天的收益
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);

                //当前持有股票，有两种可能
                //昨天就持有，今天选择观望，收益为到昨天的收益dp[i-1][j][1]
                //昨天没有持有股票，今天买了，收益为到昨天的收益减去今天买到的股票价格dp[i-1][j][0]-prices[i-1]
                //两者取较大的收益作为今天的收益
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
            }
        }
        return dp[N][K][0];
    }
}