<p>There are <code>n</code> soldiers standing in a line. Each soldier is assigned a <strong>unique</strong> <code>rating</code> value.</p>

<p>You have to form a team of 3 soldiers amongst them under the following rules:</p>

<ul>
	<li>Choose 3 soldiers with index (<code>i</code>, <code>j</code>, <code>k</code>) with rating (<code>rating[i]</code>, <code>rating[j]</code>, <code>rating[k]</code>).</li>
	<li>A team is valid if: (<code>rating[i] &lt; rating[j] &lt; rating[k]</code>) or (<code>rating[i] &gt; rating[j] &gt; rating[k]</code>) where (<code>0 &lt;= i &lt; j &lt; k &lt; n</code>).</li>
</ul>

<p>Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> rating = [2,5,3,4,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> rating = [2,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> We can&#39;t form any team given the conditions.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> rating = [1,2,3,4]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == rating.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= rating[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the integers in <code>rating</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    int countR(vector<int>& rating, int idx, int sortType, int count,
               int last) {
        if (count == 0) {
            return 1;
        }
        if (idx == 0) {
            return 0;
        }
        if (sortType == 0) {
            return countR(rating, idx - 1, 0, count, last) +
                   countR(rating, idx - 1, 1, count - 1, idx - 1) +
                   countR(rating, idx - 1, 2, count - 1, idx - 1);
        }
        if (sortType == 1 && rating[idx - 1] < rating[last]) {
            return countR(rating, idx - 1, 1, count, last) +
                   countR(rating, idx - 1, 1, count - 1, idx - 1);
        }
        if (sortType == 2 && rating[idx - 1] > rating[last]) {
            return countR(rating, idx - 1, 2, count, last) +
                   countR(rating, idx - 1, 2, count - 1, idx - 1);
        }
        return countR(rating, idx - 1, sortType, count, last);
    }
    int countM(vector<int>& rating, int idx, int sortType, int count, int last,
               vector<vector<vector<vector<int>>>>& dp) {
        if (count == 0) {
            return 1;
        }
        if (idx == 0) {
            return 0;
        }
        if (dp[idx][sortType][count][last] != -1) {
            return dp[idx][sortType][count][last];
        }
        if (sortType == 0) {
            return dp[idx][sortType][count][last] =
                       countM(rating, idx - 1, 0, count, last, dp) +
                       countM(rating, idx - 1, 1, count - 1, idx - 1, dp) +
                       countM(rating, idx - 1, 2, count - 1, idx - 1, dp);
        }
        if (sortType == 1 && rating[idx - 1] < rating[last]) {
            return dp[idx][sortType][count][last] =
                       countM(rating, idx - 1, 1, count, last, dp) +
                       countM(rating, idx - 1, 1, count - 1, idx - 1, dp);
        }
        if (sortType == 2 && rating[idx - 1] > rating[last]) {
            return dp[idx][sortType][count][last] =
                       countM(rating, idx - 1, 2, count, last, dp) +
                       countM(rating, idx - 1, 2, count - 1, idx - 1, dp);
        }
        return dp[idx][sortType][count][last] =
                   countM(rating, idx - 1, sortType, count, last, dp);
    }
    int countT(vector<int>& rating) {
        vector<vector<vector<vector<int>>>> dp(
            rating.size() + 1,
            vector<vector<vector<int>>>(
                3, vector<vector<int>>(4, vector<int>(rating.size() + 1, 0))));
        for (int idx = 0; idx <= rating.size(); idx++) {
            for (int sortType = 2; sortType >= 0; sortType--) {
                for (int last = 0; last <= rating.size(); last++) {
                    dp[idx][sortType][0][last] = 1;
                }
            }
        }
        for (int idx = 1; idx <= rating.size(); idx++) {
            for (int sortType = 2; sortType >= 0; sortType--) {
                for (int count = 1; count <= 3; count++) {
                    for (int last = 0; last <= rating.size(); last++) {
                        if (sortType == 0 || last == rating.size()) {
                            dp[idx][0][count][last] =
                                dp[idx - 1][0][count][last] +
                                dp[idx - 1][1][count - 1][idx - 1] +
                                dp[idx - 1][2][count - 1][idx - 1];
                        } else if (sortType == 1 &&
                                   rating[idx - 1] < rating[last]) {
                            dp[idx][1][count][last] =
                                dp[idx - 1][1][count][last] +
                                dp[idx - 1][1][count - 1][idx - 1];
                        } else if (sortType == 2 &&
                                   rating[idx - 1] > rating[last]) {
                            dp[idx][2][count][last] =
                                dp[idx - 1][2][count][last] +
                                dp[idx - 1][2][count - 1][idx - 1];
                        } else {
                            dp[idx][sortType][count][last] =
                                dp[idx - 1][sortType][count][last];
                        }
                    }
                }
            }
        }
        return dp[rating.size()][0][3][rating.size()];
    }
    int countO(vector<int>& rating) {
        vector<vector<vector<int>>> dp(
            3, vector<vector<int>>(4, vector<int>(rating.size() + 1, 0))),
            temp(3, vector<vector<int>>(4, vector<int>(rating.size() + 1, 0)));
        for (int idx = 0; idx <= rating.size(); idx++) {
            for (int sortType = 2; sortType >= 0; sortType--) {
                for (int last = 0; last <= rating.size(); last++) {
                    dp[sortType][0][last] = 1;
                    temp[sortType][0][last] = 1;
                }
            }
        }
        for (int idx = 1; idx <= rating.size(); idx++) {
            for (int sortType = 2; sortType >= 0; sortType--) {
                for (int count = 1; count <= 3; count++) {
                    for (int last = 0; last <= rating.size(); last++) {
                        if (sortType == 0 || last == rating.size()) {
                            temp[0][count][last] = dp[0][count][last] +
                                                   dp[1][count - 1][idx - 1] +
                                                   dp[2][count - 1][idx - 1];
                        } else if (sortType == 1 &&
                                   rating[idx - 1] < rating[last]) {
                            temp[1][count][last] =
                                dp[1][count][last] + dp[1][count - 1][idx - 1];
                        } else if (sortType == 2 &&
                                   rating[idx - 1] > rating[last]) {
                            temp[2][count][last] =
                                dp[2][count][last] + dp[2][count - 1][idx - 1];
                        } else {
                            temp[sortType][count][last] =
                                dp[sortType][count][last];
                        }
                    }
                }
            }
            dp=temp;
        }
        return dp[0][3][rating.size()];
    }
    int numTeams(vector<int>& rating) {
        // return countR(rating,rating.size(),0,3,rating.size());

        // vector<vector<vector<vector<int>>>> dp(
        //     rating.size()+1, vector<vector<vector<int>>>(
        //         3, vector<vector<int>>(
        //             4, vector<int>(rating.size()+1,-1)
        //         )
        //     )
        // );
        // return countM(rating,rating.size(),0,3,rating.size(),dp);

        // return countT(rating);

        return countO(rating);
    }
};
14956