题目

Implement pow(x, n).

解答

直接用递归法：

//递归法（"折半"递归，不要用常规的一个个乘，效率非常低）
public class Solution {
    public double pow(double x, int n) {
        if(n==0)
            return 1;
        if(n==1)
            return x;
        if(n==-1)
            return 1/x;
        if(n%2==0){
            double tmp=pow(x,n>>1);     //降低子递归
            return tmp*tmp;
        }else{
            return pow(x,n-1)*x;
        }
    }
}

若n比較小的时候，能够使用DP法，有效缓存DP的数组。性能会远超递归。当然递归也是有优点的，假设n非常大，而且x不确定时，数组的空间会不够。这时就仅仅能递归了。（此题DP法不能通过， pow(0.00001, 2147483647)，应该是数组不能开太大）

//DP法：


double pow(double x,int n){
	boolean isPositive=false;
	if(n==0)
		return 1;
	else if(n<0){
		isPositive=true;
		n*=-1;
	}
	double[] result=new double[n+1];
	result[1]=x;
	for(int i=2;i<=n;i++){
		if(i%2==0){
			result[i]=result[i/2]*result[i/2];
		}else{
			result[i]=result[i-1]*x;
		}
	}
	if(isPositive)
		return 1/result[n];
	else
		return result[n];
}