1. 最长回文子串（LeetCode 5）
问题描述:
给定一个字符串，找出最长的回文子串。
解题思路:
使用动态规划建立一个二维表格
dp[i][j]，表示子串S[i:j+1]是否为回文串。根据dp[i][j]的值来决定dp[i][j+1]的值。
#include <stdio.h>
#include <string.h>
#include <stdbool.h>// 检查字符串s[i:j+1]是否为回文串
bool isPalindrome(char *s, int i, int j) {while (i < j) {if (s[i] != s[j]) return false;i++;j--;}return true;
}// 动态规划求解最长回文子串
char* longestPalindrome(char* s) {int len = strlen(s);if (len == 0) return "";int dp[len][len];memset(dp, 0, sizeof(dp));int start = 0; // 记录最长回文子串的起始位置int maxLength = 1; // 记录最长回文子串的长度// 单字符回文串for (int i = 0; i < len; i++) {dp[i][i] = 1;}// 双字符回文串for (int i = 0; i < len - 1; i++) {if (s[i] == s[i + 1]) {dp[i][i + 1] = 1;start = i;maxLength = 2;}}// 长于2个字符的回文串for (int length = 3; length <= len; length++) {for (int i = 0; i < len - length + 1; i++) {int j = i + length - 1;if (s[i] == s[j] && dp[i + 1][j - 1]) {dp[i][j] = 1;start = i;maxLength = length;}}}char* result = (char*)malloc((maxLength + 1) * sizeof(char));strncpy(result, s + start, maxLength);result[maxLength] = '\0';return result;
}int main() {char s[] = "babad";char* result = longestPalindrome(s);printf("Longest Palindromic Substring: %s\n", result);free(result);return 0;
}
2. 编辑距离（牛客网）
问题描述:
给定两个字符串，求将一个字符串转换成另一个字符串所需的最少操作数（插入、删除、替换）。
解题思路:
使用二维动态规划表格
dp[i][j]，表示word1[0:i-1]和word2[0:j-1]的编辑距离。根据插入、删除、替换操作更新dp[i][j]。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>// 动态规划求解编辑距离
int minDistance(char* word1, char* word2) {int m = strlen(word1);int n = strlen(word2);int dp[m + 1][n + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j;} else if (j == 0) {dp[i][j] = i;} else {int cost = (word1[i - 1] == word2[j - 1]) ? 0 : 1;dp[i][j] = fmin(fmin(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);}}}return dp[m][n];
}int main() {char word1[] = "intention";char word2[] = "execution";printf("Edit Distance: %d\n", minDistance(word1, word2));return 0;
}
3. 最大子数组和（牛客网）
问题描述:
给定一个整数数组，找出具有最大和的连续子数组。
解题思路:
使用一维动态规划数组
dp，其中dp[i]表示以第i个元素结尾的最大子数组和。递推关系为dp[i] = max(dp[i-1] + nums[i], nums[i])
#include <stdio.h>
#include <limits.h>// 动态规划求解最大子数组和
int maxSubArray(int* nums, int numsSize) {int maxSum = nums[0];int currentSum = nums[0];for (int i = 1; i < numsSize; i++) {currentSum = fmax(nums[i], currentSum + nums[i]);maxSum = fmax(maxSum, currentSum);}return maxSum;
}int main() {int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int size = sizeof(nums) / sizeof(nums[0]);printf("Maximum Subarray Sum: %d\n", maxSubArray(nums, size));return 0;
}
4. 最长递增子序列（牛客网）
问题描述:
给定一个整数数组，找到其中最长递增子序列的长度。
解题思路:
使用一维动态规划数组
dp，其中dp[i]表示以第i个元素结尾的最长递增子序列的长度。递推关系为dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]。
#include <stdio.h>
#include <limits.h>// 动态规划求解最长递增子序列
int lengthOfLIS(int* nums, int numsSize) {if (numsSize == 0) return 0;int dp[numsSize];int length = 1;dp[0] = 1;for (int i = 1; i < numsSize; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;}}if (length < dp[i]) {length = dp[i];}}return length;
}int main() {int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};int size = sizeof(nums) / sizeof(nums[0]);printf("Length of Longest Increasing Subsequence: %d\n", lengthOfLIS(nums, size));return 0;
}
5. 0-1 胶囊问题（牛客网）
问题描述:
给定一个背包的容量和一组物品的重量及价值，求最大总价值。
解题思路:
使用二维动态规划表格
dp[i][w]，表示前i个物品中背包容量为w时的最大价值。递推关系为dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])。
#include <stdio.h>
#include <string.h>
#include <algorithm>#define MAX_ITEMS 100
#define MAX_CAPACITY 100// 动态规划求解0-1背包问题
int knapsack(int weight[], int value[], int n, int capacity) {int dp[MAX_ITEMS][MAX_CAPACITY] = {0};for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {if (weight[i-1] <= w) {dp[i][w] = std::max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1]);} else {dp[i][w] = dp[i-1][w];}}}return dp[n][capacity];
}int main() {int weight[] = {1, 2, 3};int value[] = {60, 100, 120};int n = sizeof(weight) / sizeof(weight[0]);int capacity = 5;printf("Maximum value in Knapsack = %d\n", knapsack(weight, value, n, capacity));return 0;
}
6. 矩阵的最小路径和（牛客网）
问题描述
给定一个二维矩阵
grid，每个格子里有一个非负整数。你需要从矩阵的左上角 (0,0) 开始，移动到右下角 (m-1,n-1)，每次只能向右或向下移动一步，计算从左上角到右下角的最小路径和。
输入
- 一个
m x n的二维矩阵grid，其中grid[i][j]表示第i行第j列的格子的值。
输出
- 从左上角到右下角的最小路径和。
示例
输入:
[
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
输出:
7
解释:
最优路径是：1 → 3 → 1 → 1 → 1，总路径和为 7。
解题思路
这个问题可以使用动态规划（DP）解决。定义一个二维数组
dp，其中dp[i][j]表示从起点到(i, j)的最小路径和。状态转移方程如下：
- 如果只考虑从上方和左方的移动：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])其中
dp[i-1][j]是从上方来的路径和，dp[i][j-1]是从左方来的路径和。
#include <stdio.h>
#include <limits.h>#define MAX_ROWS 100
#define MAX_COLS 100// 动态规划求解矩阵的最小路径和
int minPathSum(int grid[MAX_ROWS][MAX_COLS], int m, int n) {int dp[MAX_ROWS][MAX_COLS];dp[0][0] = grid[0][0];for (int i = 1; i < m; i++) {dp[i][0] = dp[i-1][0] + grid[i][0];}for (int j = 1; j < n; j++) {dp[0][j] = dp[0][j-1] + grid[0][j];}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = grid[i][j] + (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);}}return dp[m-1][n-1];
}int main() {int grid[MAX_ROWS][MAX_COLS] = {{1, 3, 1},{1, 5, 1},{4, 2, 1}};int m = 3, n = 3;printf("Minimum Path Sum: %d\n", minPathSum(grid, m, n));return 0;
}
