给定一个匹配词说“bad”和列表中的词“bird”、“cat”、“mug”、“thug”、“irk”、“kin”、“in”、“mad”、“md”的词尝试形成匹配词。每次您在给定列表中使用单词时，您都会得到一分。不匹配的字母将带有负分。所以目标是在这场比赛中最大化积分。
"bad" = "bird" -> "ir" + "a" + 1 point
"ir" = "irk" - "k" + 1 point
"k" = "kin" - "in" + 1 point
"in" = "in" + 1 point
"a" = -1 point
总分 = 3 分。
找到一个算法（可能递归）来找到最好的分数。
我迷失了从未评估的表达式列表中找出来，选择最好的一个来达到最佳分数。例如在上面的例子中，如果我首先评估“a”而不是“ir”，我会得到不同的结果。
计划以这种方式实施（我相信 LISP 会以更干净的方式做到这一点）
int max_score = 0;
// 以 expr_list 开头包含一个元素，即 match_word
int get_score(node *word_list, node *expr_list, int recursion_depth) {
int score = 0;
node *left_expr, *right_expr;
if(!word_list || recursion_depth > 5) {
return -list_size(expr_list);
}
else if (!expr_list) {
return 0;
}
word_list = find_next_unvisted(word_list);
while(expr_list) {
while(word_list) {
left_expr = elem_split_left(word_list, expr_list);
right_expr = elem_split_right(word_list, expr_list);
list_add(expr_list, left_expr);
list_add(expr_list, right_expr);
expr_list->visited = 1;
word_list->visited = 1;
prev_score = score;
score++;
score += get_score(find_next_unvisited(word_list), find_next_unvisited(expr_list), ++recursion_depth);
if(score > max_score) {
max_score = score;
}
else { /* start backtracking */
expr_list->visited = 0;
word_list->visited = 0;
// Undo elem split
list_delete(expr_list, left_expr);
list_delete(expr_list, right_expr);
score = prev_score;
}
word_list = find_next_unvisted(word_list);
}
expr_list = find_next_unvisited(expr_list);
}
free_list(word_list);
free_list(expr_list);
return max_score;
}