[数据结构与算法]LeetCode50. 动态规划方法求阶乘

leetcode 50 pow(x, n)

三种解决思路

1. 调用库函数
2. 暴力迭代
3. 分治法(本文方法)

• 1， 2就不用说了， 第三种分治法，分治法本质上是一种动态规划方法，例如2的十次方求法可以先求 2的5次方， 再求2的2次方。 需要注意的是2的5次方和2的2次方不需要求2次，而是使用备忘录将求过的子问题进行记录，下一次求求解时直接使用。

• count变量和前三个函数式为了打印递归层次帮助理解的

var count = 0

func printIndent(){
	fmt.Printf("%v", ">")
	for i:=0;i < count;i++{
		fmt.Printf("%v", "  >")
	}
}

func leftIndent(format string, params ...interface{}){
	printIndent()
	fmt.Printf(format+"\n", params... )
	count --
}

func rightIndent(format string, params ...interface{}){
	count++
	printIndent()
	fmt.Printf(format+"\n", params... )
}

func myPow(x float64, n int) float64{
	mem:=make(map[int]float64)
	if n<0{
		return 1/myPowFunc(x, -n, mem)
	}
	return myPowFunc(x, n, mem)
}

func myPowFunc(x float64, n int, mem map[int]float64) float64  {
	rightIndent("n = %v", n)
	if n==0{
		leftIndent("return:  %v", 1)
		return 1
	}
	if n==1{
		leftIndent("return:  %v", x)
		return x
	}
	if n==-1{
		leftIndent("return: %v", 1/x)
		return 1/x
	}
	if ret, ok:=mem[n];ok{
		leftIndent("return: %v", ret)
		return ret
	}
	if n&1==1{
		mem[n] = myPowFunc(x, n/2, mem)*myPowFunc(x, n/2, mem)*x
	}else{
		mem[n] = myPowFunc(x, n/2, mem)*myPowFunc(x, n/2, mem)
	}

	leftIndent("return: %v", mem[n])
	return mem[n]
}

以2¹⁰ 为例，打印结果可以清晰看到递归层次和备忘录的作用

			>  >n = 10
			>  >  >n = 5
			>  >  >  >n = 2
			>  >  >  >  >n = 1
			>  >  >  >  >return:  2
			>  >  >  >  >n = 1
			>  >  >  >  >return:  2
			>  >  >  >return: 4
			>  >  >  >n = 2
			>  >  >  >return: 4
			>  >  >return: 32
			>  >  >n = 5
			>  >  >return: 32
			>  >return: 1024

性能