[算法]爱奇艺笔试题，赛车进站问题

Question

upadate： 应该是我想复杂了， 没有考虑到最后一圈需要进站的情况， 也就是说跑完最后一圈也要在站里，
那么就不能按我下面的“PS”来考虑，感谢各位， n为4到时候应该是为7

假设一场赛车比赛中需要跑n圈， 而某赛车最多跑3圈就需要进站加油继续跑， 输出有多少种进站策略， 比如n为3的时候输出为4 （题设中的样例）。 我的思路好像有点问题， 只AC了25%，估计是错了：

function getCount(n){
        var  dict = {0:1,1:1,2:3,3:4}
        var  rest = n % 3
        var  sum = Math.pow(4,(n - rest)/3)
        return sum*dict[rest]
}

————————以下应该是错的，因为按这种逻辑n为3的情况下就得是7了，不符合样例-————————————————
PS:我觉得不是简单的上楼梯之类的，比如n为4的时候下面回答输出为7， 肯定不止7种啊， 我列举出来你看， n为4的时候， 只进1次的策略有2种（2，3），只进2次的策略有5种（12，13，23，24，34），进3次的策略有4种（123，134，234，124），剩下进4次的策略有1种，加起来就有2+5+4+1 = 12种了

Answer 1

//https://leetcode.com/problems/combination-sum-iv/    
var combinationSum = function(nums, target) {
    // ans[i] 表示组成 i 的方案数
    var ans = [];
    ans[0] = 1;
    for (var i = 1; i <= target; i++) {
        ans[i] = 0;
        for (var j = 0, len = nums.length; j < len; j++) {
            var item = nums[j];
            if (i - item < 0)
                continue;
            // (i - item) + item = i
            ans[i] += ans[i - item];
        }
    }
    return ans[target];
};
combinationSum([1, 2, 3], 4)

Answer 2

分治+深度探索的算法可以解决

思路很简单，假设我们行n圈的方案叫 cardGame(n)
n=0，返回0
n=1，返回1
n=2，返回2
n=3，返回4
n=4的时候，

假如我们第一次走1圈，那么剩下的情况就是n=3的情况了，
假如我们第一次走2圈，那么剩下的情况就是n=2的情况了，
假如我们第一次走3圈，那么剩下的情况就是n=1的情况了，
即n=4等于 cardGame(3)+cardGame(2)+cardGame(1)

n=5也可以拆分成以上的情况
递归的思路就是

function cardGame(n){
    switch(n){
        case 0:
        case 1:
        case 2:
            return n;
        case 3:
            return 4;
        default:
            var r = 0;
            for(var i=1;i<=3;i++){
                r+=cardGame(n-i)
            }
            return r
    }
}

这种方法思路很容易想到，但是效率不高。而慕少艾的方法是其改进版。

还有一种非常数学的方法是利用矩阵的，你搜索一下 斐波那契数列
当然那个是2维的，你这题是3维的，不过按照线性代数的原则是可以做出来的，但是本人智商有限，不清楚具体怎么做。

Answer 3

F(n) = F(n-1)+F(n-2)+F(n-3)
F(0) = 1, F(1) = 2, F(2) = 4, F(3)=7
递归公式的理解：假设第一次进站是在第一、二、三圈时，分别对应的是F(n-1)、F(n-2)、F(n-2)

Answer 4

感觉很牛逼的样子啊,没懂,进站策略是什么意思?n=4,结果就为1啊(跑四圈,最少要进一次站),咋为7呢?握草这逻辑是什么鬼?这是什么面试题?估计我连大门都进不去啊...

Answer 5

其实我连题目都没看懂，比如需要跑4圈，最多跑了3圈就得进站，那进站了不是比赛结束了吗，后面的怎么跑？

Answer 6

function getCount(n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  if (n == 3) return 4;
  return getCount(n - 1) + getCount(n - 2) + getCount(n - 3);
}

思路如上，性能上还可以优化

以下会输出组合方案

function getDetail(n) {
  if (n == 1) return [[1]];
  if (n == 2) return [[1,1], [2]];
  if (n == 3) return [[1,1,1], [1,2], [2,1], [3]];

  // 获取n-d情况下的所有方案，然后在前面都加一个d，获得n情况下第一次跑了d圈再进站的所有情况，d=1,2,3
  function getPrefixedDetail(d) {
    return getDetail(n - d).map(function(i) { return [d].concat(i); });
  }
  return getPrefixedDetail(1).concat(getPrefixedDetail(2)).concat(getPrefixedDetail(3));
}

n = 5时, count = 13, 方案如下
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2

Answer 7

就是使用一步两步和三步有几种上楼梯的方法。

def getStop(n):
    stops = [0] * (n + 1)
    stops[0] = 1
    if n >= 1:
        stops[1] = 1
    if n >= 2:
        stops[2] = 2
    for circle in range(3, n + 1):
        stops[circle] = stops[circle - 3] + stops[circle - 2] + stops[circle -1]
    return stops[n]

Answer 8

利用迭代，
第一次可以1.2.3
以后还可以1.2.3
最后加和是n
也就是f(n)=f(n-1)+f(n-2)+f(n-3)

if(n==1)return1
if(n==2)return2
if(n==3)return4

Answer 9

1 1
2 1-1 2
3 1-1-1 1-2 2-1 3
4 1-1-1-1 1-2-1 2-2 1-1-2 1-3 3-1
即：n的最大因子为3的...怎么称呼忘了...反正你错了...

Answer 10

问题描述确定没问题吗？

赛车在比在中加油应该尽量少加油，所以n为3的时候，赛车不加油就能跑下来，结果应该是0吧。

n==4的时候，最少加油一次，结果是3（第1圈结束加油，或第2圈结束加油，或第3圈结束加油）；

n==5的时候，最少加油一次，结果是2（第二圈结束，或第三圈结束）。

总的来说应该是让加油次数最少