计算n的k次方最少需要多少次乘法？
k=2的时候显然一次，3的时候两次
4的时候也是两次：
n*n=n^2
n^2*n^2=n^4
分别计算2，4，8，16...次幂然后乘到结果当然是很快的，这也是常见的快速幂做法，但不是最快，比如k=15的时候只需要5次：
n*n=n^2
n^2*n=n^3
n^3*n^3=n^6
n^6*n^6=n^12
n^12*n^3=n^15
对于任意k，目前好像并没有一个计算最少乘法次数的方法
==========================
看评论区的一些同学好像很多都低估了这题的难度，其实这个题像很多数论题一样，没啥规律可循，数字比较小的时候好像有规律，大一点就不行了，具体的论述资料可以看高大爷写的《计算机程序设计艺术》第二卷第四章，虽然书老了点，但我目前还没有得到这个题目被解决的消息，至少它在相当长的时间都难住了很多数学家
说DP可解的，我觉得这题并不是一个dp模型，或者说就算能套用一个dp模型，计算量也是很大的，如果你觉得dp可以很快解决，或你能想出很快解决的其他算法，不如做一下这个题： Problem 122 - Project Euler题面很简单，设m(k)表示n^k最少需要的乘法数量，求∑m(k)，1≤k≤200
====================
经评论提醒，这个问题是这个链接： Addition chain - Wikipedia其中有这句话：There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage.
转播
