人生的烦恼,多在于知道的太多,而做的太少。

杨辉三角 的算法实现

算法 zhangman523@gmail.com 2717℃ 0评论

杨辉三角 的算法实现

杨辉三角形是排列成三角形的一系列数字。 在杨辉三角形中,每一行的最左边和最右边的数字总是 1。 对于其余的每个数字都是前一行中直接位于它上面的两个数字之和。

下面给出一个5行的杨辉三角:

yanghuiTrangle

基本情况

可以看到,每行的最左边和最右边的数字是基本情况,在这个问题中,它总是等于 1。
因此,我们可以将基本情况定义如下:

f(i,j) = 1 where j=1 or j=i

递推关系

让我们从杨辉三角形内的递推关系开始。
首先,我们定义一个函数 f(i, j)它将会返回杨辉三角形第 i 行、第 j 列的数字。

我们可以用下面的公式来表示这一递推关系:

f(i,j)=f(i?1,j?1)+f(i?1,j)

java 实现

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

示例:

方法一 迭代实现


方法二 递归实现


在上面的例子中,您可能已经注意到递归解决方案可能会导致一些重复的计算,例如,我们重复计算相同的中间数以获得最后一行中的数字。 举例说明,为了得到 f(5, 3) 的结果,我们在 f(4, 2) 和 f(4, 3) 的调用中计算了 f(3, 2) 两次。下面我们优化递归算法

方法三 递归+记忆化


拓展算法


给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

示例:

转载请注明:zhangman523 » 杨辉三角 的算法实现

喜欢 (3)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址