赛车进站问题

「爱情、让人受尽委屈。」 2022-07-16 06:49 162阅读 0赞

假设一场赛车比赛中需要跑 n 圈，而某赛车最多跑 3 圈就需要进站加油继续跑，请问有多少种进站策略。

# 分析 #

跑 n 圈加油的策略函数getCount(n)如下：

1.  当 n = 0 时，返回值为 0；赛车不跑圈，则没有进站策略。
2.  当 n = 1 时，返回值为 1；赛车跑1圈，则进站加油和不加油都可以，其策略只能为1。
3.  当 n = 2 时，返回值为 2；赛车跑2圈，第1圈跑完进站加油或不加油两种选择，跑完第2圈后比赛结束并不关心加油问题，所以其加油策略仅与第一圈进站加油与否有关，因此其策略为2。
4.  当 n = 3 时， 返回值为 4；赛车跑3圈，第1圈跑完进站加油或不加油两种选择，第2圈跑完进站加油或不加油两种选择，那么跑完第3圈已经结束不关心加油问题，所以其加油的策略仅与前两圈有关，那么其策略为2\*2 = 4。
5.  当 n = 4 时：  
    假设赛车第一次跑1圈后进站加油，那么剩下的加油策略就是 n=3 时，赛车进站加油的策略。  
    假设赛车第一次跑2圈后进站加油 ，那么剩下的加油策略就是 n = 2 时，赛车进站加油的策略。  
    假设赛车第一次跑3圈后进站加油，那么剩下的加油策略就是 n = 1时，赛车进站加油的策略。  
    所以，n = 4 时，赛车的加油策略数为getCount(4-1)+getCount(4-2)+getCount(4-3)。
6.  当 n = N 时，赛车的加油策略为getCount(N-1)+getCount(N-2)+getCount(N-3)

# 实现 #

// 递归实现
    int getCount(int n) {
        if (n < 3) return n;
        if (n == 3) return 4;
    
        return getCount(n-1) + getCount(n-2) + getCount(n-3);
    }
    
    // 迭代实现
    int getCount(int n) {
        if (n < 3) return n;
        if (n == 3) return 4;
    
        int t1 = 1,  t2 = 2, t3 = 4;
        int cnt = 0;
        for (int i = 4; i <= n; i++) {
            cnt = t1 + t2 + t3;
            t1 = t2;
            t2 = t3;
            t3 = cnt;
        }
        return cnt;
    }