蓝桥杯动态规划第三弹-路径问题进阶2.0-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯动态规划第三弹-路径问题进阶2.0。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、删除并获得点数

二、粉刷房子

三、买卖股票最佳时机

四、手续费的买卖股票

一、删除并获得点数

删除并且获得点数

蓝桥杯动态规划第三弹-路径问题进阶2.0,蓝桥杯,动态规划,职场和发展

（我觉得这个还是较为复杂一点的）

我是开始一点没有思路，然后放弃这个题了——后来发现他有一个重要的思路，我从来没有发现过的一个思路。

nums[1,1,2,2,4,4,5,8,8,8]，首先他假如说给这个数组，他既不完整，又不规律，很不好处理

所以我们使用类似于哈希表那种

/\arr=[0,2,4,0,8,5,0,0,24],这个下标是依次对应的，

0 1 2 3 4 5 6 7 8

这样就可以让给的数据，变成我们心中想的那样规律了。同时还有一个问题，不知道大家看出来没有，就是相同元素其实可以选择合并，假如说三个8，那么他的遇到一个，把7和9都删除了，那么后面的8就可以直接加在上面。

1.状态表示：

dp[i]:到达i位置，获得的最大点数，细分为下面两种

f[i]到达i位置,处于“选择”能获得的最大点数。

g[i]到达i位置，处于“不选“能获得的最大点数。

2.状态转移方程

f[i]=g[i-1]+nums[i]

g[i]=max(f[i-1],g[i-1])

3.初始化

f[0]=nums[0]

4.填表顺序

从左到右

5.返回值

二、粉刷房子

刷房子

蓝桥杯动态规划第三弹-路径问题进阶2.0,蓝桥杯,动态规划,职场和发展

由题意得出，红色是0，绿色是2，那么蓝色就是1

1.状态表示

dp[i]:到达i位置，花费的最小金额

可以更加细分(我的思路这样，但是有些问题，所以我这种思路不是很好

f[i]:到达i位置，处于选择状态，花费的最小金额

g[i]:到达i位置，处于不能相同颜色状态，花费的最小金额

)

细分

dp[i][0]:粉刷到i位置，最后刷墙是红色，此时的最小花费

dp[i][1]:粉刷到i位置，最后刷墙是蓝色，此时的最小花费

dp[i][2]:粉刷到i位置，最后刷墙是绿色，此时的最小花费

2.状态转移方程

dp[i][0]=min(dp[i-1][1],dp[i-1][2])

dp[i][1]=min(dp[i-1][0],dp[i-1][2])

dp[i][2]=min(dp[i-1][0],dp[i-1][1])

3.初始化

dp[0][0]=cost[0][0]

dp[0][1]=cost[0][1]

dp[0][2]=cost[0][2]

4.填表顺序

从左到右，三个表一个写

5.返回值

返回三个dp表结尾中的最小值

return min(dp[][],dp[][],dp[][])
class Solution {
    public int minCost(int[][] costs) {
    int m=costs.length,n=costs[0].length;
    int[][]dp=new int[m][n];

    dp[0][0]=costs[0][0];
    dp[0][1]=costs[0][1];
    dp[0][2]=costs[0][2];

    for(int i=1;i<m;i++){
    dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i][0];
    dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+costs[i][1];
    dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+costs[i][2];
    }
      return Math.min(dp[m-1][0],Math.min(dp[m-1][1],dp[m-1][2]));
    }
}

三、买卖股票最佳时机

买卖股票

1.状态表示

dp[i]:到达i位置，股票的最大利润

但是我们可以进行具体的细分

f[i]:第i天的时候，买入后但没有进行别的操作的状态（未卖出，手里有股票）状态的最大利润（这里你思考一下，这个卖出状态和处于冷冻期状态，有没有必要去把这两个状态更细化的区分。）

t[i]:第i天的时候，股票处于冷冻期状态

g[i]:第i天的时候，股票处于股票处于冷冻期结束，没买但是可以买的状态(手里面没股票，要去买）的最大利润

2.状态转移方程

f[i]=Math.max(f[i-1],g[i-1]-prices[i])

t[i]=f[i-1]+prices[i]

g[i]=Math.max(f[i-1],t[i-1])

3.初始化

f[0]为买入之后，所以直接赋值为-prices[0]

4.填表顺序

从左到右，三个表一个填写

5.返回值

return 三个表最大即可
class Solution {
    public int maxProfit(int[] prices) {
      int m=prices.length;
      int []f=new int[m];
      int []g=new int[m];
      int []t=new int[m];

      if(m==1){
        return 0;
      }
      f[0]=-prices[0];
      for(int i=1;i<m;i++){
   f[i]=Math.max(f[i-1],g[i-1]-prices[i]);
   t[i]=f[i-1]+prices[i];
   g[i]=Math.max(g[i-1],t[i-1]);
      }
      
    return Math.max(f[m-1],Math.max(t[m-1],g[m-1])); 
    }
}

四、手续费的买卖股票

手续费股票

蓝桥杯动态规划第三弹-路径问题进阶2.0,蓝桥杯,动态规划,职场和发展

1.状态表示

f[i]:第i天的时候，买入后但没有进行别的操作的状态（未卖出，手里有股票）状态的最大利润（这里你思考一下，这个卖出状态和处于冷冻期状态，有没有必要去把这两个状态更细化的区分。）

g[i]:第i天的时候，股票处于股票卖出但是没有进行别的操作状态，没买但是可以买的状态(手里面没股票，要去买）的最大利润

注意：是股票卖出之后支付手续费（原因其实可以看他给的例子，它是卖出减去进货，然后再去减手续费

2.状态方程

f[i]=Math.max(f[i-1],g[i-1]-prices[i])

g[i]=Math.max(f[i-1]+prices[i]-fee,g[i-1])

3.初始化

f[0]为买入之后，所以直接赋值为-prices[0]

4.填表顺序

从左到右，两个表一个填写

5.返回值

return max(f[],g[]);文章来源地址https://www.toymoban.com/news/detail-736361.html
class Solution {
    public int maxProfit(int[] prices, int fee) {
    int m=prices.length;
    int f[]=new int[m];
    int g[]=new int[m];

    f[0]=-prices[0];
    for(int i=1;i<m;i++){
    f[i]=Math.max(f[i-1],g[i-1]-prices[i]);
     g[i]=Math.max(f[i-1]+prices[i]-fee,g[i-1]);
    }
     return Math.max(f[m-1],g[m-1]); 
    }
}