题解 | #爬楼梯#Erlang动态规划拆分情况

解题思路

因为每次只能爬1或2个台阶, 从1个2个台阶开始推断, 并将问题n阶台阶拆解为求解到达n-1阶台阶以及n-2阶台阶的总和, 过程中缓存已记录阶数对应的数据

代码

-spec climb_stairs(N :: integer()) -> integer().
climb_stairs(N) when N =< 2 ->
    N;
climb_stairs(N) ->
    do_climb_stairs(3, #{stairs => N, 1 => 1, 2 => 2}).

do_climb_stairs(N, Args = #{stairs := Stairs}) when N < Stairs ->
    Sum = maps:get(N - 1, Args) + maps:get(N - 2, Args),
    do_climb_stairs(N + 1, Args#{N => Sum});
do_climb_stairs(N, Args) ->
    maps:get(N - 1, Args) + maps:get(N - 2, Args).