【算法零基础100讲题解】第四讲 组合数——基于Python语言

• 刷题格言
• 写在前面
• 题目解析
• • 1.杨辉三角（118）
  • 2.杨辉三角2（119）
• 写在后面

作为一个真正的程序员，首先应该尊重编程，热爱你所写下的程序，他是你的伙伴，而不是工具！

排列与组合是我们在高中学习到的一些知识；
今天的内容是组合数；

组合数：从n个元素里面取出m个
组合数的递推公式：

今天的题目是关于组合数在杨辉三角中的应用，题目的链接已经放在了每个题目上，点击即可自动跳转。

1.杨辉三角（118）

class Solution:
	def generate(self,numRows:int)->List[List[int]]:
		if numRows==1:
			return [[1]]
		if numRows==2:
			return [[1],[1,1]]
		ans=[[1],[1,1]]
		for i in range(2,numRows):
			ans.append([])
			for j in range(i+1):
				if j==0 or j==i:
					ans[i].append(1)
				else:
					ans[i].append(ans[i-1][j-1]+ans[i-1][j])
		return ans

杨辉三角的题目，本质考察的就是组合数中的组合数递推公式

1）这道题呢我是用了拆分，把第一行和第二行不需要进行计算的给直接拿出来；
2）我们建立一个ans的列表，里面包含了前两行的内容，之后我们对剩下的行数进行遍历，依次求出每行的数；
3）循环内嵌套了另一个循环，因为杨辉三角两侧的数均为1，在这里我用了if条件判断，之后用递推公式算出来每个值。

2.杨辉三角2（119）

不仔细看的话会感觉这道题目和以上题目是完全一样的，其实也确实没有太大的差别；
经过对比，第一题中是行数，第二题中是索引；
第一题中让我们返回所有的行数，第二题中只返回给定索引的行数。
解题思路与核心代码与上题一样；
最后记得返回当前索引的行即可。

今天只有两道题目，且两个题目的核心部分也是一样的，帮助我们学习了组合数以及其在题目中的应用，这部分相较于昨天还是比较轻松的！
如果看到这里了，不妨点个赞再走吧！