给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。 请你采取最优策略分割 s ，使剩下的字符 最少 。c语言实现

以下是使用动态规划算法，采用 C 语言实现的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000
#define MAX_WORD_LENGTH 50
#define INF 0x3f3f3f3f

int dp[MAX_N + 1];
char s[MAX_N + 1];
char dictionary[MAX_N][MAX_WORD_LENGTH + 1];
int word_count;

typedef struct TrieNode {
    int is_word;
    struct TrieNode* children[26];
} TrieNode;

TrieNode* create_trie_node() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->is_word = 0;
    memset(node->children, 0, sizeof(node->children));
    return node;
}

void insert_word(TrieNode* root, char* word) {
    TrieNode* node = root;
    while (*word) {
        int idx = *word - 'a';
        if (!node->children[idx]) {
            node->children[idx] = create_trie_node();
        }
        node = node->children[idx];
        ++word;
    }
    node->is_word = 1;
}

int search_word(TrieNode* root, char* word) {
    TrieNode* node = root;
    while (*word) {
        int idx = *word - 'a';
        if (!node->children[idx]) {
            return 0;
        }
        node = node->children[idx];
        ++word;
    }
    return node->is_word;
}

int main() {
    scanf("%s", s);
    scanf("%d", &word_count);
    TrieNode* root = create_trie_node();
    for (int i = 0; i < word_count; ++i) {
        scanf("%s", dictionary[i]);
        insert_word(root, dictionary[i]);
    }
    int n = strlen(s);
    memset(dp, INF, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] != INF && search_word(root, s + j, i - j)) {
                dp[i] = dp[i] < dp[j] + i - j ? dp[i] : dp[j] + i - j;
            }
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

其中，我们使用了一个 Trie 树来存储字典中的单词， Trie 树是一种高效的数据结构，可以用来快速查找字符串。在 insert_word 函数中，我们依次遍历要插入的单词的每一个字符，将其插入到 Trie 树中，如果该节点的 children 数组中没有对应的字符，则新建一个 TrieNode 节点。在 search_word 函数中，我们依次遍历要查询的字符串的每一个字符，判断该字符在当前节点的 children 数组中是否存在，如果存在，则继续遍历，否则返回 0。

在主函数中，我们首先读入字符串 s 和字典 dictionary，然后依次将字典中的单词插入到 Trie 树中。接下来，我们使用动态规划算法，定义一个数组 dp，其中 dp[i] 表示将字符串 s 的前 i 个字符分割成若干个互不重叠的子字符串，每个子字符串都在字典 dictionary 中出现过，剩余的字符数最少是多少。初始时，我们将 dp 数组中所有元素的值都赋为 INF，表示目前还没有找到符合要求的分割方案。接下来，我们使用双重循环来遍历字符串 s 中的所有子串，判断每个子串是否在字典 dictionary 中出现过，并且以该子串为结尾的字符串能否被拆分。如果可以，更新 dp 数组的值。最终，当 dp[n] 的值不为 INF 时，表示字符串 s 可以被拆分成若干个互不重叠的子字符串，使得每个子字符串都在字典 dictionary 中出现过，剩余的字符数最少是 dp[n]。

时间复杂度为 O(n^3)，空间复杂度为 O(n^2)，其中 n 是字符串 s 的长度。