LeetCode 309. 买卖股票的最佳时机含冷冻期. a    原题链接    中等

作者： 作者的头像   牢景又双叒叕站起来了 ,  2024-10-20 16:28:43 ,  所有人可见 ,  阅读 11

1


题目描述

blablabla

样例

class Solution {
    public int maxProfit(int[] prices) {
         int n=prices.length;
        int dp[][]= new int [n+2][2];
        // dp[0][0] = -prices[0];//这个初始化代码 关键  因为第0个没有进入循环 只是作为基础输入
        //i+1的写法  其实仅仅是防止下标越界的辅助操作而已  适用于 给出数组0-n-1的情况 
        //现在的dp[0]相当于-1  表示的是不合法的情况  表示啥也没开始
        //插入两个状态 dfs(−2,0)=0 dfs(−1,0)=0
       //这是合法的  为了让第0天可以买股票
        dp[1][1]=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){

             dp[i+2][1]=Math.max(dp[i+1 ][1],dp[i ][0]-prices[i]);
              dp[i+2][0]=Math.max(dp[i+1][0],dp[i+1][1]+prices[i]);
        }
        return dp[n+1][0];//最后一个有效下标是n-1
    }
}
blablabla

1 评论

用户头像

class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
int dp[][]= new int [n+1][2];
// dp[0][0] = -prices[0];//这个初始化代码 关键 因为第0个没有进入循环 只是作为基础输入
//i+1的写法 其实仅仅是防止下标越界的辅助操作而已 适用于 给出数组0-n-1的情况
//现在的dp[0]相当于-1 表示的是不合法的情况 表示啥也没开始
int p[]=new int [n+1];
for(int i=0;i<n;i) p[i+1]=prices[i];
dp[0][1]=Integer.MIN_VALUE;
for(int i=1;i<=n;i){

          dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+p[i]);
          //问题  第一个股票不能从买转移过来了
           if(i==1)
         dp[i][1]=Math.max(dp[i-1 ][1],dp[i-1 ][0]-p[i]);

          if(i>=2)  dp[i][1]=Math.max(dp[i-1 ][1],dp[i-2 ][0]-p[i]);
    }
    return dp[n][0];//最后一个有效下标是n-1


}

}