C++刷leetcode（1395. 统计作战单位数）【动态规划】

糖逗

题目描述：

1.  n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
   
2. 
   
3. 每 3 个士兵可以组成一个作战单位，分组规则如下：
   
4. 
   
5. 从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
   
6. 作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中&#160; 0&#160;<= i <&#160;j <&#160;k <&#160;n
   
7. 请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
   
8. 
   
9. &#160;
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：rating = [2,5,3,4,1]
    
14. 输出：3
    
15. 解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
    
16. 示例 2：
    
17. 
    
18. 输入：rating = [2,1,3]
    
19. 输出：0
    
20. 解释：根据题目条件，我们无法组建作战单位。
    
21. 示例 3：
    
22. 
    
23. 输入：rating = [1,2,3,4]
    
24. 输出：4
    
25. &#160;
    
26. 
    
27. 提示：
    
28. 
    
29. n == rating.length
    
30. 1 <= n <= 200
    
31. 1 <= rating[i] <= 10^5
    
32. 
    
33. 来源：力扣（LeetCode）
    
34. 链接：https://leetcode-cn.com/problems/count-number-of-teams
    
35. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int numTeams(vector<int>& rating) {
   
4.         int len = rating.size();
   
5.         vector<vector<vector<int> > > dp(len, vector<vector<int> >(3, vector<int>(2, 0)));
   
6.         for(int i = 0; i < len;i ++){
   
7.             dp[i][0][0] = 1;
   
8.             dp[i][0][1] = 1;
   
9.         }
   
10.         for(int i = 0; i < len; i++){
    
11.             for(int j = 0; j < i; j++){
    
12.                 if(rating[j] < rating[i]){
    
13.                     for(int k = 1; k < 3; k++){
    
14.                         dp[i][k][1] += dp[j][k-1][1];
    
15.                     }
    
16.                 }else if(rating[j] > rating[i]){
    
17.                     for(int k = 1; k < 3; k++){
    
18.                         dp[i][k][0] += dp[j][k-1][0];
    
19.                     }
    
20.                 }
    
21.             }
    
22.         }
    
23.         int res = 0;
    
24.         for(int i = 0; i < len; i++){
    
25.             res += dp[i][2][0];
    
26.             res += dp[i][2][1];
    
27.         }
    
28.         return res;
    
29.     }
    
30. };

复制代码

注意事项：
1. dp[i][j][k]表示以rating[i]为结尾的j长度递增或递减的总数（k=0表示递减，k=1表示递增）

糖逗