2023年第十四届蓝桥杯javaB组 蜗牛解题思路（动态规划 O（n））

蜗牛要到达第i根竹竿(传送门或底部)，必然要经过第i-1根竹竿。

可知第一根竹竿可以初始化为：

footMin[0]=pos[0]*1.0;doorMin[0]=pos[0]+door[0]*1.0/0.7;

这里先讨论第i根竹竿的传送门距离原点的最小时间doorMin[i]的情况。

从第i-1根竹竿到第i根竹竿的传送门有两种情况:

                1.花费doorMin[i-1]的时间到达第i-1根竹竿的传送门，然后到达第i根竹竿的height[i-1]高度，向上或向下爬行(door[i]-height[i-1])/0.7秒或(height[i-1]-door[i])/1.3秒的时间，这里以height[i-1]<=door[i]，向上爬行为例，到达传送门。

                2.花费doorMin[i-1]的时间，到达第i-1根竹竿的底部，直接爬行，经过pos[i]-pos[i-1]秒的时间到达 foot[i]=的底部，再向上爬行(door[i]/0.7)秒的时间到达传送门。

得出doorMin[i]的动态转移方程:

        以door[i]>height[i-1]为例:

        footDistance=pos[i]-pos[i-1];

        doorMin[i]=Min(doorMin[i-1]+(door[i]-height[i-1])/0.7,  footMin[i-1]+footDistance+door[i]/0.7);

然后讨论footMin[i]的情况：

同理，从第i-1根竹竿到第i根竹竿的底部有两种情况:

                1.花费doorMin[i-1]的时间,到达第i-1根竹竿的传送门，然后到达第i根竹竿的height[i-1]高度，向下爬行(height[i-1])/1.3秒的时间，到达第i根竹竿的底部。

                2.花费footMin[i-1]的时间,到达第i-1根竹竿的底部，直接爬行，经过pos[i]-pos[i-1]秒的时间到达 第i根竹竿的底部。

得出footMin[i]的动态转移方程:

        footMin[i]=Min(doorMin[i-1]+height[i-1]/1.3,  footMin[i-1]+footDistance);

经历一次循环后，footMin[n-1]就是蜗牛从原点到达第n根竹竿的最短时间。

代码：

//这里从1开始，因为i=0是初始化条件。//以n-1为终点，因为n-1的下标代表第n个竹竿    for (int i=1;i=door[i]){//传送过来后的高度比门高            doorMin[i]=Math.min(doorMin[i-1]+(height[i-1]-door[i])*1.0/1.3,              footMin[i-1]+footDistance+door[i]*1.0/0.7);        }else{    //传送过来后的高度比门低            doorMin[i]=Math.min(doorMin[i-1]+(door[i]-height[i-1])*1.0/0.7,              footMin[i-1]+footDistance+door[i]*1.0/0.7);        }                    //求footMin[i]                    footMin[i]=Math.min(doorMin[i-1]+height[i-1]*1.0/1.3,              footMin[i-1]+footDistance*1.0);    }    System.out.println(String.format("%.2f",footMin[n-1]));

优化：

对于时间复杂度来说O(n)已经无法优化，

对于空间复杂度O(n)也无法优化:

但是可以减小两个数组空间的开销。

              用preFoot来代替minFoot[i-1], nowFoot来替代minFoot[i];

              用preDoor来代替minDoor[i-1], nowDoor来替代minDoor[i];

因为我们并不关心i-1之前的数据，可直接用迭代法代替。

创作不易，点赞收藏加关注！！！

来源地址：https://blog.csdn.net/m0_71102533/article/details/130035823