6-11 删除字符 分数 10

这道题目的意思是，给定一个字符串，删除其中的某些字符，使得剩下的字符串是原字符串的子序列，并且被删除的字符数量最少。其中，子序列是指原字符串中的一些字符按照原来的顺序排列而成的新的字符串，可以不连续。

具体的解题方法可以使用动态规划来实现，设 $dp[i][j]$ 表示原字符串的前 $i$ 个字符和新字符串的前 $j$ 个字符的最长公共子序列的长度，则有状态转移方程：

$$ dp[i][j] = \begin{cases} 0 & i=0 \text{ or } j=0 \\ dp[i-1][j-1]+1 & s[i] = t[j] \\ \max(dp[i-1][j], dp[i][j-1]) & s[i] \neq t[j] \end{cases} $$

其中，$s$ 和 $t$ 分别表示原字符串和新字符串，$s[i]$ 表示原字符串中的第 $i$ 个字符，$t[j]$ 表示新字符串中的第 $j$ 个字符。

最终的答案是原字符串的长度减去最长公共子序列的长度，即 $len(s)-dp[len(s)][len(t)]$。

如果您需要更详细的解释，请让我知道。

相关问题

7-2 删除字符串中指定字母 分数 20 作者 齐心 单位 湖北汽车工业学院 请使用指针的方法编写程序，程序的功能是从键盘输入一个字符串(字符串长度小于100)，删除其中的字母a后输出。例如，输入字符串abcaca，输出bcc。 输入样例: abcaca

以下是实现删除字符串中指定字母的代码：

#include <stdio.h>

int main() {
    char str[100];
    char *p = str;
    gets(str); // 输入字符串
    while (*p != '\0') { // 遍历字符串
        if (*p != 'a') { // 如果不是字母a，则输出该字符
            printf("%c", *p);
        }
        p++; // 指针后移
    }
    return 0;
}

该程序使用指针p遍历输入的字符串，如果当前字符不是字母a，则输出该字符。最后输出的字符串中就不包含字母a了。需要注意的是，输入的字符串应该使用gets函数读入，因为使用scanf函数读入字符串时无法读入空格。

6-2 14.3.2 删除字符串中的指定字符 分数 10 作者 chanel 单位 中国地质大学（北京） 编写函数deleteChar，用于删除字符串（传长不超过100）中指定的字符，将字符 串中与指定字符(非空格字符）相同的字符全部删除。 函数接口定义： void deleteChar(char *s, char c); 其中 s 是用户传入的字符数组的首地址，c是待删除的字符。 裁判测试程序样例： #include <iostream> using namespace std; void deleteChar(char *s, char c); int main() { char *str, ch; str=new char[81]; cin.getline(str,80); cin>>ch; deleteChar(str, ch); cout<<str; delete []str; return 0; } /* 请在这里填写答案 */ 输入格式： 第一行字符串。 第二行输入待删除字符ch。 输出格式： 输出删除所有ch字符后的字符串。 输入样例1： I Llove Lyou. L 输出样例1： I love you.

以下是函数deleteChar的实现：

void deleteChar(char *s, char c) {
    int i, j;
    for (i = j = 0; s[i] != '\0'; i++) {
        if (s[i] != c) {
            s[j++] = s[i];
        }
    }
    s[j] = '\0';
}

主要思路是使用两个指针 i 和 j，遍历字符串 s，当 s[i] 不等于待删除字符 c 时，将其复制到 s[j]，然后 j 自增。最后在 s[j] 的位置添加字符串结束符 '\0'。