java - 需要帮助理解三步动态编程/递归问题

Question

我一直在努力学习/理解更多的动态编程/递归，但我不确定如何理解它为何有效。我正在研究这个

https://www.geeksforgeeks.org/count-ways-reach-nth-stair-using-step-1-2-3/

链接中有解决方案。我理解递归到一定程度，但我不理解程序的结构如何给出你想要的结果。我只是，不明白为什么

return findStep(n - 3) +  
       findStep(n - 2) + 
       findStep(n - 1);   

解决这个问题，或者别人怎么知道它会给你所有的可能性。

代码的内存部分稍后展示，但我只想展示基础知识。

感谢任何帮助，谢谢!

Answer 1

为了那些没有关注您的链接的人的利益，您要解决的问题是通过一次跳上 1、2 或 3 步来找出有多少种不同的爬楼梯方式(任意组合)。

让我们使用符号 f(x) 来表示爬楼梯的可能方式的数量 x 步，并假设你我在 n 级楼梯的底部。您的下一步行动有以下三种选择:

• 如果您上一级台阶，那么从您的新位置将有f(n-1) 种可能的爬楼梯方式。

• 如果您上两级台阶，那么将有f(n-2)种可能的方式从您的新位置爬楼梯。

• 如果您上三级台阶，那么从您的新位置将有f(n-3) 种可能的爬楼梯方式。

如果所有这三个 Action 都是可能的，那么 f(n) 的值必须等于 f( n-1) + f(n-2) + f(n-3) .这是递归算法的基础。您只需提供终点:

• f(1) = 1(上升 1 步)

• f(2) = 2(上升 2 步，或 1+1 步)

• f(3) = 4(上升 3 或 2+1 或 1+2 或 1+1+1 步)

如果愿意，您还可以添加条件 f(0) = 1(即，有一种方式不爬楼梯)。您链接到的页面中的代码似乎已将 f(3) 和 f(0) 的结果折叠在一起，但结果是一样的。

由于此递归算法在每次迭代时调用自身 3 次，因此除非您存储 f(x) 的中间值，否则它将运行非常缓慢。这就是动态规划中的记忆化。