第二题蒙了一会，题主代码肯是对的，但总感觉自己不太踏实，后来索性证明一下~ -------------------------------------- 直觉是动态规划, 子问题拆解碰到问题: 从第N层到第i层, 方式只可能有三条: 1)先到第i-1层, 再上一层, 即d[i-1]+1 2)先到i+1层, 再下一层, 即d[i+1]+1 3)如果i是偶数, 还可能是从i/2层坐电梯上来, 即d[i/2]+1 但这样d[i]依赖d[i+1]无法使用动态规划(d为最短路径函数) 下面证明方式2中到i+1层的方式一定是坐电梯直接到的, 否则一定不是最短路径: 要到i+1层同样只有三种方式: 1)从第i层上来, 不可能 快递员要到i层, 因此不可能是从i层走上来的, 除非傻了 2)从坐电梯到第i+1+k层走下来, 注意下楼只有一种方式, 一定是一路走下来 2.1)如果i为偶数, k定为奇数, 总路程s1为: d[(i+1+k)/2]+1+(k+1) 到第i/2层的最短路径一定小于等于先到d[i/2+(k+1)/2]再下楼到i/2层, 因为这是其中的一条路径 即, d[i/2] <= d[i/2+(k+1)/2] + (k+1)/2 因此先到i/2层再坐电梯到i层的路程s2有: s2 = d[i/2]+1 <= d[i/2+(k+1)/2]+1+(k+1)/2 <d[(i+1+k)/2]+1+(k+1) = s1 所以此时s1一定不是最短路径 2.2)如果i为奇数, k一定为偶数, 总路程s1为: d[(i+1+k)/2]+1+(k+1) 到(i+1)/2层的最短路径一定小于等于其中的一条: 到(i+1)/2+k/2层然后再走下楼 即: d[(i+1)/2] <= d[(i+1)/2+k/2]+k/2 因此因此先到(i+1)/2层再坐电梯到i+1层再到第i层的路程s2有: s2 = d[(i+1)/2] + 1 + 1 <= d[(i+1)/2+k/2]+k/2+1+1 <= d[(i+1+k)/2]+1+(k+1)=s1 当且仅当k=0时等号成立 2.3)综上, 最短路径中, 到i+1层然后下楼到i层只有一种情况, 即先坐电梯到i+1层然后走下来