สมมติว่ามีตัวเลข n เราต้องหาแถวที่ n (0-indexed) ของสามเหลี่ยมปาสคาล สามเหลี่ยมปาสคาลสร้างได้ดังนี้
- แถวบนสุดคืออาร์เรย์ [1]
- แถวถัดไปสร้างโดยการบวกตัวเลขด้านบนซ้ายกับด้านบนขวา
เช่น ถ้าอินพุตคือ 4 ผลลัพธ์จะเป็น [1, 4, 6, 4, 1]
ขั้นตอนการแก้ปัญหา
- ถ้า n == 0 คืนค่า [1]
- ถ้า n == 1 คืนค่า [1,1]
- ls := [1,1], temp := [1,1]
- for i ในช่วง 2 ถึง n+1 ทำ
- ls := temp
- temp := [1]
- for i ในช่วง 0 ถึง len(ls)-1 ทำ temp.append(ls[i] + ls[i+1])
- temp.append(1)
- คืนค่า temp
ตัวอย่างโค้ด
class Solution:
def solve(self, n):
if n == 0:
return [1]
if n == 1:
return [1, 1]
ls = [1, 1]
temp = [1, 1]
for i in range(2, n+1):
ls = temp
temp = [1]
for i in range(len(ls)-1):
temp.append(ls[i] + ls[i+1])
temp.append(1)
return temp
ob = Solution()
print(ob.solve(4))
อินพุต
4
เอาต์พุต
[1, 4, 6, 4, 1]
