題目描述

有這么一款單人卡牌游戲，牌面由顏色和數(shù)字組成，顏色為紅、黃、藍(lán)、綠中的一種，數(shù)字為 0?9 中的一個(gè)。游戲開始時(shí)玩家從手牌中選取一張卡牌打出，接下來如果玩家手中有和他上一次打出的手牌顏色或者數(shù)字相同的手牌，他可以繼續(xù)將該手牌打出，直至手牌打光或者沒有符合條件可以繼續(xù)打出的手牌。

現(xiàn)給定一副手牌，請(qǐng)找到最優(yōu)的出牌策略，使打出的手牌最多。

輸入描述

第一行是每張手牌的數(shù)字，數(shù)字由空格分隔

第二行為對(duì)應(yīng)的每張手牌的顏色，用 rybg 這 4 個(gè)字母分別代表 4 種顏色，字母也由空格分隔。

手牌數(shù)量不超過10。

輸出描述

輸出一個(gè)數(shù)字，即最多能打出的手牌的數(shù)量。

示例1

輸入：
1 4 3 4 5
r y b b r

輸出：
3

說明：
如果打(1,r）-> (5,r)，那么能打兩張。如果打(4，y) -> (4,b) -> (3,b)，那么能打三張。

示例2

輸入：
1 2 3 4
r y b l

輸出：
1

說明：
沒有能夠連續(xù)出牌的組合，只能在開始時(shí)打出一張手牌，故輸出 1 。

題解

題目類型： 深度優(yōu)先搜索（DFS）

解題思路：

1. 通過深度優(yōu)先搜索遍歷所有可能的出牌組合。
2. 維護(hù)一個(gè)全局變量 maxCnt，記錄最多能打出的手牌數(shù)。
3. 遞歸函數(shù) dfs 中，遍歷未使用過的手牌，判斷是否能打出。如果可以，標(biāo)記為已使用，繼續(xù)遞歸下一層。
4. 在遞歸的過程中更新 maxCnt。
5. 最終返回 maxCnt。

時(shí)間復(fù)雜度： 搜索的時(shí)間復(fù)雜度取決于搜索空間的大小，最壞情況下為 O(2^n)，其中 n 為手牌數(shù)量。每張牌有兩種狀態(tài)：打出或不打出。

空間復(fù)雜度： 遞歸調(diào)用的深度為手牌數(shù)量，因此空間復(fù)雜度為 O(n)。

C++

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

template <typename T>
vector<T> readList() {
    string input;
    getline(cin, input);
    stringstream stream(input);
    vector<T> result;
    T value;
    while (stream >> value) {
        result.push_back(value);
    }
    return result;
}

int maxCnt;

void dfs(int prev, int cnt, vector<int>& nums, vector<string>& colors, vector<bool>& vis) {
    // 更新最多可以打出的手牌數(shù)
    maxCnt = max(cnt, maxCnt);

    for (size_t cur = 0; cur < nums.size(); cur++) {
        if (vis[cur]) continue;

        // 之前未打出牌 或 和前面牌數(shù)相同 或 和前面牌顏色相同
        if (prev == -1 || nums[prev] == nums[cur] || colors[prev] == colors[cur]) {
            vis[cur] = true;
            dfs(cur, cnt + 1, nums, colors, vis);  // 打出當(dāng)前的牌
            vis[cur] = false;
        }
    }
}

int main() {
    // 讀取卡牌數(shù)字列表
    vector<int> nums = readList<int>();

    // 讀取卡牌顏色列表
    vector<string> colors = readList<string>();

    maxCnt = 0;

    // 調(diào)用 dfs 方法求解并輸出結(jié)果
    vector<bool> vis(nums.size(), false);
    dfs(-1, 0, nums, colors, vis);
    cout << maxCnt << endl;

    return 0;
}

希望這個(gè)專欄能讓您熟練掌握算法, ?????? 立即訂閱。

整理題解不易， 如果有幫助到您，請(qǐng)給點(diǎn)個(gè)贊 ???? 和收藏 ?，讓更多的人看到。??????