以下文章来源于小K算法 ，作者小K算法
小K算法 .
曾就职华为和美团，中山大学数学与计算机系本科，专注分享数学、算法、科学等硬核知识
来自公众号：小K算法
设f[i][0]，f[i][1]，f[i][2]分别表示：第i步向东、向西、向北走的不同路线总数。
则有如下递推关系：
第i步向东，等于上一步向东和向北之和，即f[i][0] = f[i - 1][0] + f[i - 1][2]
第i步向西，等于上一步向西和向北之和，即f[i][1] = f[i - 1][1] + f[i - 1][2]
第i步向北，等于上一步向东，向西，向北之和，即f[i][2] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2];
int f[100][3] = {0};
f[0][0] = 1;
f[0][1] = 1;
f[0][2] = 1;
for (int i = 1; i < n; ++i) {
f[i][0] = f[i - 1][0] + f[i - 1][2];
f[i][1] = f[i - 1][1] + f[i - 1][2];
f[i][2] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2];
}
cout << f[n - 1][0] + f[n - 1][1] + f[n - 1][2] << endl;
int s[100];
s[0] = 1;
s[1] = 3;
for (int i = 2; i < n; ++i) {
s[i] = 2 * s[i - 1] + s[i - 2];
}
cout << s[n - 1] << endl;
文章首发平台：微信公众号【小K算法】。
网友评论已有0条评论, 我也要评论