Solution Idea

50058. Word Selection

用遞迴的方法找出所有子集合並判斷其是否包含26個字母和其cost。

以下幾點同學容易犯錯:

1.無止盡的遞迴。

2.cost初值錯誤。

3.傳進遞迴涵數的陣列與涵數外的陣列是同一個,謹慎使用。

4.TLE。每次遞迴call自己超過兩次。無效遞迴過多,例如少了下面程式碼中dfs()的第一個if。

以下提供一個同學寫的程式碼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <string.h>
 
int N, cost[22], len[22], min=2147483647;
char _string[22][52];
 
void dfs(int idx, int _cost, int appear[128], int t) {
    if (_cost > min)
        return;
    if (idx == N) {
        int valid = 1;
        for (int i='a'; i<='z' && valid; i++) {
            valid &= (appear[i]==1);
        }
        if (valid && (_cost < min)) {
            min = _cost;
        }
        return;
    }
    int tmp[128];
    for (int i='a'; i<='z'; i++)
        tmp[i] = appear[i];
    dfs(idx+1, _cost, tmp, t+1);
    for (int i=0; i<len[idx]; i++) {
        appear[_string[idx][i]] = 1;
    }
    dfs(idx+1, _cost+cost[idx], appear, t+1);
    return;
}
 
int main() {
    scanf("%d", &N);
    for (int i=0; i<N; i++) {
        scanf("%s %d", _string[i], &cost[i]);
        len[i] = strlen(_string[i]);
    }
    int appear[128];
    dfs(0,0, appear, 0);
    printf("%d", min);
    return 0;
}

Discussion