AcWing 1055. JAVA dp状态机模型- 股票买卖 II    原题链接    简单

作者： 作者的头像   acw_weian ,  2020-06-17 19:12:07 ,  所有人可见 ,  阅读 722

0


ABC.png 


import java.io.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010, INF = 0x3f3f3f3f;
    static int[][] dp = new int[N][2];
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        int[] a = new int[n + 1];
        String[] ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            a[i] = Integer.valueOf(ss[i - 1]);
        }
        for(int i = 0; i <= n; i++){
            dp[i][0] = -INF;
            dp[i][1] = -INF;
        }
        dp[0][0] = 0;

        for(int i = 1; i <= n; i++){
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - a[i]);
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + a[i]);
        }

        System.out.println(dp[n][0]);


    }

}

4 评论

用户头像
一念花开   2020-06-27 17:15         踩      回复

dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-a[i]);//手上持有股票，只能是从前面没有股票时转移过来，买股票后的收益
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+a[i]);//手上没有股票，只能从前面的有股票时转移过来，卖掉股票后的收益

用户头像
acw_weian   2020-06-30 21:28         踩      回复

dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-a[i]); //手上持有股票，可以从之前持有股票和之前没有股票新买了股票两种状态转移过来，
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+a[i]);//手上没有股票，也可以从之前持有股票卖出股票和之前没有股票两种状态转移过来

用户头像
一念花开   2020-06-27 17:02         踩      回复

dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - a[i]);//这里表示买入股票吗？
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + a[i]);//这里表示卖出股票吗？

用户头像
acw_weian   2020-06-30 21:30         踩      回复

dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - a[i]); dp[i - 1][1] 表示前一天或之前手上持有股票，没有卖出， 题目没有说一定要在买了股票后的第二天卖出， 所以一只股票可以持有多天。