面試題-上台階實現

語言: CN / TW / HK

題目名

台階有n階,一個人上台階,可以一次上1階,可以一次上2階,也可以一次上3階,問上這個n級的台階一共有多少種走法?

解決方案

  • 實際上是考核函數遞歸
  • 先分析前面幾種情況
  • 假如台階有1階,有1種走法
  • 假如台階有2階,有2種走法
  • 假如台階有3階,有4種走法
  • 假如台階有4階,有7種走法
  • 假如台階有5階,有13種走法
  • 仔細分析會發現n大於3階時,n階的走法是前面n-1、n-2和n-3的總和。我們把走n階看成是f(n)的函數,如果先走1階,則後面的n-1階有函數f(n-1)種走法,先走2階後面的n-2階有函數f(n-2)種走法,同理先走3階剩餘的n-3階有函數f(n-3)種走法。用公式表示為f(n)=f(n-1)+f(n-2)+f(n-3)。
//台階有n階,一個人上台階,可以一次上1階,可以一次上2階,也可以一次上3階,問上這個n級的台階一共有多少種走法?
func CptaijieNum(n int64) int64 {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2 //1,1; 2
	}
	if n == 3 {
		return 4 // 1,1,1; 1,2; 2,1;3

	}
	return CptaijieNum(n-1) + CptaijieNum(n-2) + CptaijieNum(n-3)
}
func TestCptaijieNum(t *testing.T) {
	i := CptaijieNum(5)
	fmt.Println("走法:", i)
}