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

问题描述

问 题

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种了

解决方案

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

这篇关于[算法]爱奇艺笔试题，赛车进站问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！