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

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]; } }