之前面试碰到一个算法题，自己实现了一版但是效率堪忧，求优化建议[已解决]

你这个写法算是暴力破解，是有改进空间的，你的思路是正确的，用了树的结构，但是你可以思考下，这棵树是不是有相同的路径，这些相同的路径是不是可以“剪枝”？比如 1+19 和 19 +1 是一样的，但是在树中就重复了，你可以使用一个“备忘录”来记录已存在的路径，这样就大大减少了重复。

力扣里面有一个爬楼梯的算法,跟这个很像,每次可以走1步或者2步,然后有45层楼梯怎么爬?

@QJAutumn 对 感觉能用动态规划做出来，但是这个题分析不出来 :joy:

你这个算法错了

直接找出通项公式？感觉和之前做的一道题很像，就通过掷6面骰子，有多少种可能到达距离起始点N格的地方：

- def ways(n):
-     A = 3**(n+6)
-     M = A**6 - A**5 - A**4 - A**3 - A**2 - A - 1
-     return pow(A, n+6, M) % A

- for i in xrange(20):
-     print i, '->', ways(i)

这个和斐波那契类似吧。

f(20) = f(19) + f(18) + f(17) + f(16) + f(15) + f(14)

可以先算出 f(1) 至 f(6) ，再求更大的就行了吧！

@鲜橙多 如果不同的顺序也算的话，那就是类似斐波那契数列的那种，可以自底向上来分析。
如果要凑出1，只有一种情况，掷骰子1点；
如果凑出2，就是两种情况，1+1和2；
如果凑出3，就是 1+1+1 、 1+2 和 2+1 和 3 四种情况，有没有发现，凑 3 的时候，用到了 凑2时候的组合，所以计算3的时候，不需要再从1开始算，直接使用刚才算2的时候的情况，也就是： 当第一次为1，剩余3-1=2，这个2刚才计算过了，2种情况，那么第一次为1的时候有两种，第一次为2的时候，剩余 3-2=1,1刚才也计算过了，只有一种情况，还有第一次掷出3，那么得出3就有 2+1+1 三种，4也是同理，首次为1,4-1=3，有4种，首次为2,4-2=2，有2种，首次为3,4-3=1，有一种，首次为4又一种，得出4就有 3+2+1+1=7种情况
那么往后的每种情况，都可以先分析分为 第一次为1,、第一次为2、第一次为3。。。。依次类推一直到第一次为6，那么就可以写出函数：

    function count($n)
    {
        if ($n < 0) {
            return false;
        }
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return 1;
        }
        if ($n === 2) {
            return 2;
        }

        $count = 0;

        // 如果小于骰子最大可掷出点数，就会多一种情况
        if ($n <= 6) {
            $count ++;
        }
        for ($i = 1; $i <= 6; $i++) {
            if ($n-$i > 0) {
                $count += $this->count($n-$i);
            }
        }

        return $count;
    }

不过这么写还是有很多重复计算，所以可以新引入一个备忘录，来记录已经计算过的值，也就是我们常说的“空间换时间”

    public function count($n, &$map)
    {
        if ($n < 0) {
            return false;
        }

        if (isset($map[$n])) {
            return $map[$n];
        }

        $count = 0;

        // 如果小于骰子最大可掷出点数，就会多一种情况
        if ($n <= 6) {
            $count ++;
        }
        for ($i = 1; $i <= 6; $i++) {
            if ($n-$i > 0) {
                $count += $this->count($n-$i, $map);
            }
        }
        // 每次计算都记录 map
        $map[$n] = $count;

        return $count;
    }

    public function index()
    {
        // 定义备忘录
        $map = [];
        $map[0] = 0;
        $map[1] = 1;
        $map[2] = 2;
        $res = $this->count(5, $map);
    }

这样的话时间复杂度直接降为O(n)

不知道顺序有没有关系，比如你说的 18个1点和1个2点， 投掷 2 点在中间，是算1种？还是算多种呢？

20点，最多投掷 20次， 每次最小点数 1 点

20点，最少投掷 4次，63+21=20 共 4次

然后把 4次到 20 次的次数算出来 相加，

就是不知道有没有更好的

根据楼上大佬 @如梦又似幻 的思路分析出了以下公式

/**
 * f(0) = 0
 * f(1) = 1;
 * f(2) = f(1) + 1
 * f(3) = f(2) + f(1) + 1
 * f(4) = f(3) + f(2) + f(1) + 1
 * f(5) = f(4) + f(3) + f(2) + f(1) + 1
 * f(6) = f(5) + f(4) + f(3) + f(2) + f(1) + 1
 * f(7) = f(6) + f(5) + f(4) + f(3) + f(2) + f(1)
 * f(8) = f(7) + f(6) + f(5) + f(4) + f(3) + f(2)
 * 
 * 得到以下公式
 * 
 * n <= 6 f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + 1 
 * n >  6 f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-6);
 */

代码实现

<?php

class Touzi
{
    public $map = [];

    public function f($n)
    {
        if (isset($this->map[$n - 1])) {
            return $this->map[$n - 1];
        }
        $fn = 0;
        if ($n <= 6) {
            for ($i = 1; $i < $n; $i++) {
                $fn = $fn + $this->f($n - $i);
            }
            $fn = $fn + 1;
        } else {
            for ($i = 1; $i <= 6; $i++) {
                $fn = $fn + $this->f($n - $i);
            }
        }
        $this->map[$n - 1] = $fn;
        return $fn;
    }
}

$touzi = new Touzi();
echo "组合数: " . $touzi->f(50); // 389043663364337
// var_dump($touzi->map);

附上同事用动态规划的解法 :+1: 太强了

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        long result = combinationSum(new long[]{1, 2, 3, 4, 5, 6}, 50);
        System.out.println(result);
    }

    public static long combinationSum(long[] nums, int target) {
        Arrays.sort(nums);
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int rest = 1; rest <= target; rest++) {
            for (int i = 0; i < nums.length && nums[i] <= rest; i++) {
                dp[rest] += dp[(int)(rest - nums[i])];
            }
        }
        return dp[target];
    }
}

class N
{
    public $old = [];
    function getNum($sum)
    {
        $count = isset($this->old[$sum]) ? $this->old[$sum] : 0;
        if ($count == 0) {
            for ($i = 1; $i < 7; $i++) {
                $need = $sum - $i;
                if ($need == 0) {
                    $count += 1;
                } elseif ($need > 0) {
                    $count += $this->getNum($need);
                }
            }
            $this->old[$sum] = $count;
        }
        return $count;
    }
}

动态规划的版本也写出来了，根据上面第二个公式。 :smile:

<?php

function f($n)
{
    $dp = [0, 1, 2, 4, 8, 16, 32];
    if ($n < 7) {
        return $dp[$n];
    }
    for ($i = 7; $i <= $n; $i++) {
        $count = 0;
        for ($j = 1; $j <= 6; $j++) {
            $count += $dp[$j];
        }
        $dp[] =   $count;
        array_shift($dp);
    }
    return $dp[6];
}

echo f(50);

你这个顺序不同的需要去重吗？

function f($n)
{
    $dp = [0, 1, 2, 4, 8, 16, 32];
    if ($n < 7) {
        return $dp[$n];
    }
    for ($i = 7; $i <= $n; $i++) {
        $count = 0;
        for ($j = 1; $j <= 6; $j++) {
            $count += $dp[$j];
        }
        $dp[] =   $count;
        array_shift($dp);
    }
    return $dp[6];
}

function fm($n)
{
    $dp = [0, 1, 2, 4, 8, 16, 32,63];
    if ($n < 7) {
        return $dp[$n];
    }
    for ($i = 8; $i <= $n; $i++) {
        $dp[$i] =   $dp[$i-1]*2 - $dp[$i-7];
    }
    return $dp[$n];
}
echo f(50);
echo fm(50);
echo fm(50) ==f(50);

/**
 * 当总点数为1时，有1种，即1
 * 当总点数为2时，有2种，即11、2；
 * 当总点数为3时，有4种，即111、12、21、3
 * 当总点数为4时，有8种，即1111、112、121、13、211、22、31、4
 *
 * 由此可得出规律，设n为总点数，则有2的(n-1)次方种组合
 */
function f($num)
{
    if ($num < 1) {
        return 0;
    }
    return pow (2, $num - 1);
}

echo f(4);

<?php

class Demo2
{
    /**
     * @var array|int[]
     */
    public $map = [];

    /**
     * Demo2 constructor.
     */
    public function __construct()
    {
        $this->map = [
            1 => 1,
            2 => 2,
            3 => 4,
            4 => 8,
            5 => 16,
            6 => 32,
        ];
    }

    /**
     * 题目大概是这样的：给你一个骰子（6面），可以无限制的投掷，每次投掷点数之和为总点数。
     * 现问，投掷出总点数为 20，共有多少种骰子组合。
     *
     * 动态规划组成三要素
     * 1.确定状态：
     * 即确定每个元素 f[i] 或者 fi 代表什么
     *
     * 2.最后一步：
     * 对于这道题，虽然我们不知道最优策略是什么，但是最优策略肯定是骰子投掷 k 次，a1, a2, ....ak点数和加起来是20
     * 所以一定存在最后一次的投掷点数 ak，排除最后一次投掷点数 ak，前面投掷的点数和为 20-ak
     * 关键点一
     *   虽然现在不知道 k 和 ak，但是我们确定前 k-1 次投掷出了总点数 20-ak
     *
     * 3.子问题
     * 现在的问题是有多少种骰子组合可以投掷出总点数 20-ak，原问题是有多少种骰子组合可以投掷出总点数 20
     * 我们将原问题转化了一个子问题，而且规模更小 20-ak，为了简化定义， 我们定义状态 f(n)=x 多少种骰子组合投掷出总点数 n
     * 我们还不知道最后一次投掷的点数 ak是多少，但是最后一次投掷的点数只能是 1 2 3 4 5 6
     * 如果 ak=1，f(20)=f(20-1) 前 k-1 次投掷出点数和 19，最后一次投掷出点数 1
     * 如果 ak=2，f(20)=f(20-2) 前 k-1 次投掷出点数和 18，最后一次投掷出点数 2
     * 如果 ak=3，f(20)=f(20-3) 前 k-1 次投掷出点数和 17，最后一次投掷出点数 3
     * 如果 ak=4，f(20)=f(20-4) 前 k-1 次投掷出点数和 16，最后一次投掷出点数 4
     * 如果 ak=5，f(20)=f(20-5) 前 k-1 次投掷出点数和 15，最后一次投掷出点数 5
     * 如果 ak=6，f(20)=f(20-6) 前 k-1 次投掷出点数和 14，最后一次投掷出点数 6
     * 所以骰子组合总数 f(20) = f(20-1) + f(20-2) + f(20-3) + f(20-4) + f(20-5) + f(20-6)
     *
     * 转移方程
     * 设状态f(n)=投掷出总点数 n 的骰子组合数，对于任意的 n：f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5) + f(n-6)
     *
     * 初始条件和边界情况
     * n-1 n-2 n-3 n-4 n-5 n-6 <0 怎么办？什么时候停下来？
     */
    public function fn($n)
    {
        if ($n <= 0) {
            return 0;
        }
        if ($n <= 6) {
            return $this->map[$n];
        }
        for ($i = 1; $i <= $n; $i++) {
            if (!isset($this->map[$i])) {
                $this->map[$i] = $this->map[$i - 1] + $this->map[$i - 2] + $this->map[$i - 3] + $this->map[$i - 4] + $this->map[$i - 5] + $this->map[$i - 6];
            }
        }
        return $this->map[$n];
    }
}

$fn = (new Demo2())->fn(20);

echo "组合数: $fn";