杨辉三角形 - 西北工业大学题解：求助递归超时_P1392

zx142407789

TA的个人主页 >

文章

粉丝

获赞

访问

4.7k

杨辉三角形 - 西北工业大学题解：求助递归超时

zx142407789

P1392 西北工业大学

发布于2024年3月20日 16:06

阅读数 221

#include<stdio.h>
int yanghui(int x, int y) {
	if (y == 0 || x == y)//第一列和对角线都是1
		return 1;
	else
		return yanghui(x - 1, y - 1) + yanghui(x - 1, y);
}
int main() {
	int n, i, j;
	while (scanf("%d", &n) != EOF) {
		for (i = 1; i < n; i++) {
			for (j = 0; j <= i; j++) {
				printf("%d ", yanghui(i, j));
			}
			printf("\n");
		}
	}
}

登录查看完整内容

登录后发布评论

2 条评论

snake

2024年3月20日 16:33

加一个数组记忆化就可以

#include<stdio.h>
int dp[50][50];
int yanghui(int x, int y) {
	if (dp[x][y] != 0) return dp[x][y]; //如果前面已经计算过了这个值
	if (y == 0 || x == y)//第一列和对角线都是1
		return 1;
	else
		return yanghui(x - 1, y - 1) + yanghui(x - 1, y);
}
int main() {
	int n, i, j;
	while (scanf("%d", &n) != EOF) {
		for (i = 1; i < n; i++) {
			for (j = 0; j <= i; j++) {
				dp[i][j] = yanghui(i, j);
				printf("%d ", dp[i][j]);
			}
			printf("\n");
		}
	}
}

zx142407789 : 回复 snake：好，谢谢大佬

2024年3月21日 14:07