动态规划

1.Trangle Problem（数字三角形问题）

#include <stdio.h>

#define ROWS 6
#define MAX_COLS 6

// 计算最小路径和并填充值表和路表
int minimumTotal(int triangle[ROWS][MAX_COLS], int valueTable[ROWS][MAX_COLS], int pathTable[ROWS][MAX_COLS]) {
	// 初始化最后一行
	for (int j = 0; j < MAX_COLS; j++) {
		valueTable[ROWS - 1][j] = triangle[ROWS - 1][j];
	}
	
	// 从倒数第二层开始向上计算
	for (int i = ROWS - 2; i >= 0; i--) {
		for (int j = 0; j <= i; j++) {
			// 当前位置的最小路径和等于当前位置的值加上下一层相邻位置的最小路径和的较小值
			valueTable[i][j] = triangle[i][j] + ((valueTable[i + 1][j] < valueTable[i + 1][j + 1]) ? valueTable[i + 1][j] : valueTable[i + 1][j + 1]);
			
			// 记录路径信息
			pathTable[i][j] = (valueTable[i + 1][j] < valueTable[i + 1][j + 1]) ? j : j + 1;
		}
	}
	
	// 返回最终结果,自底向上
	return valueTable[0][0];
}

// 打印最短路径
void printShortestPath(int triangle[ROWS][MAX_COLS], int pathTable[ROWS][MAX_COLS]) {
	int row = 0;
	printf("最短路径: %d", triangle[0][0]);
	
	for (int i = 1; i < ROWS; i++) {
		int col = pathTable[i - 1][row];
		printf(" -> %d", triangle[i][col]);
		row = col;
	}
}

int main() {
	int triangle[ROWS][MAX_COLS] = {
		{2},
		{3, 4},
		{6, 5, 7},
		{4, 1, 8, 3},
		{4, 9, 12, 15, 11},
		{12, 4, 6, 1, 9, 2}
	};
	
	int valueTable[ROWS][MAX_COLS];
	int pathTable[ROWS][MAX_COLS];
	
	int result = minimumTotal(triangle, valueTable, pathTable);
	printf("最小路径和: %d\n", result);
	
	printShortestPath(triangle, pathTable);
	
	return 0;
}

2.LCS Promblem(最长公共子序列)

#include <stdio.h>

// 计算最长公共子序列的长度
int lcs(char X[], char Y[], int m, int n) {
	int dp[m + 1][n + 1];
	
	//初始化状态表
	for(int i=0;i<=m;i++)
		for(int j=0;j<=n;j++)
			dp[i][j] = 0;
	
	// 填充动态规划表
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == 0 || j == 0)
				dp[i][j] = 0;
			else if (X[i - 1] == Y[j - 1])//最后一个相等
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
		}
	}
	
	return dp[m][n];
}

int main() {
	char X[] = "ABCBDABAABCDBABDDCBABDBCA";
	char Y[] = "BDCABAABDBCBDABDAAADCABC";
	
	int m = sizeof(X) / sizeof(X[0]) - 1;
	int n = sizeof(Y) / sizeof(Y[0]) - 1;
	
	int result = lcs(X, Y, m, n);
	
	printf("最长公共子序列的长度: %d\n", result);
	
	return 0;
}

Donate