23 动态规划解买卖股票的最佳时机含手续费

问题描述：给定一个整数数组prices，其中第i各元素代表了第i填的股票价格；非负整数fee代表了交易股票是的手续费用，你可以无限次的完成交易，但是你眉笔交易都需要付手续费，如果你已经购买了一个股票，在卖出它之前不能再继续购买股票了，返回获得利润的最大值。注意：一次交易是指买入持有并卖出股票的整个过程，你就不能再继续购买股票了。并定义卖股票才可以进行扣费。

动态规划求解：定义动态数组dp[i][0]表示第i天手里没有股票的最大值，此时有两种选择，一种是dp[i-1][1]+prices[i]-2表示在第i天卖出了股票获得了第i天的利润，第二种是不改变，与之前相同dp[i-1],dp[i][1]表示第i天手里有股票的最大值，此时有两种选择dp[i-1][0]-prices[i]或者保持dp[i-1][0]

public int maxProfit(int []prices)
{
int [][]dp=new int[prices.length][2];

dp[0][0]=0;
dp[0][1]=-prices[0];
for(int i=0;i<prices.length;i++)
{
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-2);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
}

递归方式求解：对于每一天而言：如果手上持有股票，可以选择卖或者不卖，然后进入下一天中，
如果手上没有股票，则可以选择不买或者买，然后进入下一年中，最后到达最后一天对将利润加入PriorityQueue<Integer> maxheap=new PriorityQueue<>((a,b)->{return b-a;})或者(PriorityQueue<Integer>maxheap=new PriorityQueue<>(Collections.reverseOrder()))最大堆中，最后从最大堆中弹出第一个数字即为最大利润
 

private getMaxProfit(int [] prices,int index,int profit,Boolean ishasone,PriorityQueue<Integer> queue)
{
if(index==prices.length)
{
queue.add(profit);
return;
}
if(ishasone)
{
getMaxProfit(prices,index+1,profit,ishasone);
getMaxProfit(prices,index+1,profit+prices[i]-2,!ishasone)；
}else
{
getMaxProfit(prices,index+1,profit-prices[i],!ishasone);
getMaxProfit(prices,index+1,profit,ishasone)；
}
}

public int GetMaxProfit(int []prices)
{
PriorityQueue<Integer>maxheap=new PriorityQueue<>(Collections.reverseOrder());
getMaxProfit(prices,0,0,false);
return maxheap.peek();
}

知识点总结：最小堆定义PriorityQueue<Integer>minHeap=new PriorityQueue<>();最大堆定义1
PriorityQueue<Integer>maxHeap=new PriorityQueue<>(Collections.reverseOrder());PriorityQueue<Integer>minheap=new PriorityQueue<>((a,b)->{return b-a});最大堆定义3PriorityQueue<Integer>maxHeap=new PriorityQueue<>(new Comparable<Integer>(){
@Override
public int Compare(Integer t1,Integer t2)
{
return t2-t1;
}
});
PriorityQueue增加操作：minHeap.add(),minheap.offer()
PriorityQueue减少操作：minheap.poll(),minheap.remove();会弹出
PriorityQueue查询操作:minheap.peek();

Map知识点：Map<Integer,Integer>map=new HashMap<Integer,Integer>map;
增加:Map.put(key,value);
访问:Map.get(key);
删除;Map.remove(key);
遍历：
 

        for (Integer i : Sites.keySet()) {
            System.out.println("key: " + i + " value: " + Sites.get(i));
        }
        // 返回所有 value 值
        for(String value: Sites.values()) {
          // 输出每一个value
          System.out.print(value + ", ");