三角形中的路径数
Number of Paths in a Triangle
我最近遇到了这个问题的一个更困难的变体，但意识到我无法为这个非常简单的案例生成解决方案。我搜索了 Stack Overflow，但找不到之前回答此问题的资源。
给定一个三角形 ABC，你必须计算从 'A' 开始和结束的一定长度的路径数。假设我们的函数 f(3) 被调用，它必须 return 从 A 开始和结束的长度为 3 的路径数：2 (ABA,ACA)。
我在制定优雅的解决方案时遇到问题。现在，我已经编写了一个生成所有可能路径的解决方案，但对于更大的长度，该程序太慢了。我知道一定有一个很好的动态编程解决方案可以重用我们之前计算过的序列，但我不太明白。非常感谢所有帮助。
我的笨代码：
def paths(n,sequence):
t = ['A','B','C']
if len(sequence) < n:
for node in set(t) - set(sequence[-1]):
paths(n,sequence+node)
else:
if sequence[0] == 'A' and sequence[-1] == 'A':
print sequence
我的方法是这样的：
定义 DP(l, end) = # of paths end at end and have length l
那么DP(l,'A') = DP(l-1,'B') + DP(l-1,'C'),类似DP(l,'B')和 DP(l,'C')
然后对于基本情况 即l = 1 I check if end is not 'A', then I return 0, otherwise return 1, 这样所有更大的州只计算那些开始于 'A'
答案就是调用 DP(n, 'A') 其中 n 是长度
下面是一个C++的示例代码，你可以用3调用它，它给你2作为答案；用 5 调用它，它给你 6 作为答案：
ABCBA、ACBCA、ABABA、ACACA、ABACA、ACABA
#include <bits/stdc++.h>
using namespace std;
int dp[500][500], n;
int DP(int l, int end){
if(l<=0) return 0;
if(l==1){
if(end != 'A') return 0;
return 1;
}
if(dp[l][end] != -1) return dp[l][end];
if(end == 'A') return dp[l][end] = DP(l-1, 'B') + DP(l-1, 'C');
else if(end == 'B') return dp[l][end] = DP(l-1, 'A') + DP(l-1, 'C');
else return dp[l][end] = DP(l-1, 'A') + DP(l-1, 'B');
}
int main() {
memset(dp,-1,sizeof(dp));
scanf("%d", &n);
printf("%d\n", DP(n, 'A'));
return 0;
}
已编辑
在下面回答 OP 的评论：
首先，DP（动态规划）总是关于状态的。
记住这里我们的状态是 DP(l,end)，表示长度为 l 并在 end 处结束的路径数。所以要用编程实现状态，我们通常使用数组，所以DP[500][500]没什么特别的，但space为所有可能的 l 和 end 存储状态 DP(l,end) （这就是为什么我说如果你需要更大的长度，改变数组的大小）
但是你可能会问，我理解第一个维度是l，500意味着l可以大到500，但是第二个维度呢？我只需要'A'、'B'、'C'，那为什么要用500呢？
这里还有一个技巧（C/C++），char类型确实可以默认用作int类型，其值等于它的ASCII个数。我当然不记得 ASCII table，但我知道大约 300 个就足以表示所有 ASCII 字符，包括 A(65)、B(66)、 C(67)
所以我只声明任何大到足以在第二维表示 'A'、'B'、'C' 的大小（这意味着实际上 100 已经足够了，但我只是这样做不用想那么多，声明500因为它们几乎相同，就顺序而言）
所以你问DP[3][1]是什么意思，它没有任何意义，因为当它是1时我不需要/计算第二个维度。（或者可以认为状态dp（3,1 ) 在我们的问题中没有任何物理意义)
其实我一直用65、66、67。
所以 DP[3][65] 表示长度为 3 并在 char(65) = 'A'
处结束的路径数
诀窍是不要尝试生成所有可能的序列。它们的数量呈指数增长，因此所需的内存将太大。
相反，设 f(n) 为开始和结束 A 长度为 n 的序列数，并设 g(n) 为长度为 [=] 的序列数11=] 以 A 开头但以 B 结尾。首先，明确 f(1) = 1 和 g(1) = 0。对于 n > 1，我们有 f(n) = 2g(n - 1)，因为倒数第二个字母将是 B 或 C，并且每个字母的数量相等。我们也有 g(n) = f(n - 1) + g(n - 1) 因为如果一个序列结束开始 A 结束 B 倒数第二个字母是 A 或 C.
这些规则允许您使用记忆化真正快速地计算数字。
令 PA(n) 为从 A 返回 A 的路径数，正好为 n 步。
设 P!A(n) 为从 B（或 C）到 A 的路径数，正好为 n 步。
然后：
PA(1) = 1
PA(n) = 2 * P!A(n - 1)
P!A(1) = 0
P!A(2) = 1
P!A(n) = P!A(n - 1) + PA(n - 1)
= P!A(n - 1) + 2 * P!A(n - 2) (for n > 2) (substituting for PA(n-1))
我们可以解析地求解 P!A 的差分方程，就像我们求解 Fibonacci 一样，注意 (-1)^n 和 2^n 都是差分方程的解，然后找到系数 a， b 这样 P!A(n) = a*2^n + b*(-1)^n.
我们最终得到等式 P!A(n) = 2^n/6 + (-1)^n/3，PA(n) 为 2^(n-1) /3 - 2(-1)^n/3.
这给了我们代码：
def PA(n):
return (pow(2, n-1) + 2*pow(-1, n-1)) / 3
for n in xrange(1, 30):
print n, PA(n)
给出输出：
1 1
2 0
3 2
4 2
5 6
6 10
7 22
8 42
9 86
10 170
11 342
12 682
13 1366
14 2730
15 5462
16 10922
17 21846
18 43690
19 87382
20 174762
21 349526
22 699050
23 1398102
24 2796202
25 5592406
26 11184810
27 22369622
28 44739242
29 89478486
我们可以用 for 循环解决这个问题，尽管 Anonymous 描述了一个封闭的形式。
function f(n){
var as = 0, abcs = 1;
for (n=n-3; n>0; n--){
as = abcs - as;
abcs *= 2;
}
return 2*(abcs - as);
}
原因如下：
Look at one strand of the decision tree (the other one is symmetrical):
A
B C...
A C
B C A B
A C A B B C A C
B C A B B C A C A C A B B C A B
Num A's Num ABC's (starting with first B on the left)
0 1
1 (1-0) 2
1 (2-1) 4
3 (4-1) 8
5 (8-3) 16
11 (16-5) 32
Cleary, we can't use the strands that end with the A's...
对于给定的三角形和更一般的图形，您可以比其他人发布的动态 programming/recursion 解决方案做得更好。每当您尝试计算（可能是有向的）图中的步数时，您都可以用传递矩阵的幂项来表示。设 M 是一个矩阵，其条目 m[i][j] 是从顶点 i 到顶点 j 的长度为 1 的路径数。对于三角形，传递矩阵是
0 1 1
1 0 1.
1 1 0
那么M^n是一个矩阵，其第i,j项是从顶点i到顶点j的长度为n的路径数。如果 A 对应于顶点 1，则需要 M^n 的 1,1 条目。
根据长度n-1的路径对长度n的路径计数进行动态规划和递归，相当于用n次乘法计算M^n，M * M * M * ... * M，这可以足够快。然而，如果你想计算 M^100，而不是做 100 次乘法，你可以使用 repeated squaring：Compute M, M^2, M^4, M^8, M^16, M^32, M ^64，然后是 M^64 * M^32 * M^4。对于较大的指数，乘法次数约为 c log_2(exponent)。
不是使用长度为 n 的路径由长度为 n-1 的路径和长度为 1 的步骤组成，而是使用长度为 n 的路径由长度为 k 的路径组成然后是一条长度为 n-k 的路径。
我最近遇到了这个问题的一个更困难的变体，但意识到我无法为这个非常简单的案例生成解决方案。我搜索了 Stack Overflow，但找不到之前回答此问题的资源。
给定一个三角形 ABC，你必须计算从 'A' 开始和结束的一定长度的路径数。假设我们的函数 f(3) 被调用，它必须 return 从 A 开始和结束的长度为 3 的路径数：2 (ABA,ACA)。
我在制定优雅的解决方案时遇到问题。现在，我已经编写了一个生成所有可能路径的解决方案，但对于更大的长度，该程序太慢了。我知道一定有一个很好的动态编程解决方案可以重用我们之前计算过的序列，但我不太明白。非常感谢所有帮助。
我的笨代码：
def paths(n,sequence):
t = ['A','B','C']
if len(sequence) < n:
for node in set(t) - set(sequence[-1]):
paths(n,sequence+node)
else:
if sequence[0] == 'A' and sequence[-1] == 'A':
print sequence
我的方法是这样的：
定义 DP(l, end) = # of paths end at end and have length l
那么DP(l,'A') = DP(l-1,'B') + DP(l-1,'C'),类似DP(l,'B')和 DP(l,'C')
然后对于基本情况 即l = 1 I check if end is not 'A', then I return 0, otherwise return 1, 这样所有更大的州只计算那些开始于 'A'
答案就是调用 DP(n, 'A') 其中 n 是长度
下面是一个C++的示例代码，你可以用3调用它，它给你2作为答案；用 5 调用它，它给你 6 作为答案： ABCBA、ACBCA、ABABA、ACACA、ABACA、ACABA
#include <bits/stdc++.h>
using namespace std;
int dp[500][500], n;
int DP(int l, int end){
if(l<=0) return 0;
if(l==1){
if(end != 'A') return 0;
return 1;
}
if(dp[l][end] != -1) return dp[l][end];
if(end == 'A') return dp[l][end] = DP(l-1, 'B') + DP(l-1, 'C');
else if(end == 'B') return dp[l][end] = DP(l-1, 'A') + DP(l-1, 'C');
else return dp[l][end] = DP(l-1, 'A') + DP(l-1, 'B');
}
int main() {
memset(dp,-1,sizeof(dp));
scanf("%d", &n);
printf("%d\n", DP(n, 'A'));
return 0;
}
已编辑 在下面回答 OP 的评论：
首先，DP（动态规划）总是关于状态的。
记住这里我们的状态是 DP(l,end)，表示长度为 l 并在 end 处结束的路径数。所以要用编程实现状态，我们通常使用数组，所以DP[500][500]没什么特别的，但space为所有可能的 l 和 end 存储状态 DP(l,end) （这就是为什么我说如果你需要更大的长度，改变数组的大小）
但是你可能会问，我理解第一个维度是l，500意味着l可以大到500，但是第二个维度呢？我只需要'A'、'B'、'C'，那为什么要用500呢？
这里还有一个技巧（C/C++），char类型确实可以默认用作int类型，其值等于它的ASCII个数。我当然不记得 ASCII table，但我知道大约 300 个就足以表示所有 ASCII 字符，包括 A(65)、B(66)、 C(67)
所以我只声明任何大到足以在第二维表示 'A'、'B'、'C' 的大小（这意味着实际上 100 已经足够了，但我只是这样做不用想那么多，声明500因为它们几乎相同，就顺序而言）
所以你问DP[3][1]是什么意思，它没有任何意义，因为当它是1时我不需要/计算第二个维度。（或者可以认为状态dp（3,1 ) 在我们的问题中没有任何物理意义)
其实我一直用65、66、67。 所以 DP[3][65] 表示长度为 3 并在 char(65) = 'A'
处结束的路径数诀窍是不要尝试生成所有可能的序列。它们的数量呈指数增长，因此所需的内存将太大。
相反，设 f(n) 为开始和结束 A 长度为 n 的序列数，并设 g(n) 为长度为 [=] 的序列数11=] 以 A 开头但以 B 结尾。首先，明确 f(1) = 1 和 g(1) = 0。对于 n > 1，我们有 f(n) = 2g(n - 1)，因为倒数第二个字母将是 B 或 C，并且每个字母的数量相等。我们也有 g(n) = f(n - 1) + g(n - 1) 因为如果一个序列结束开始 A 结束 B 倒数第二个字母是 A 或 C.
这些规则允许您使用记忆化真正快速地计算数字。
令 PA(n) 为从 A 返回 A 的路径数，正好为 n 步。
设 P!A(n) 为从 B（或 C）到 A 的路径数，正好为 n 步。
然后：
PA(1) = 1
PA(n) = 2 * P!A(n - 1)
P!A(1) = 0
P!A(2) = 1
P!A(n) = P!A(n - 1) + PA(n - 1)
= P!A(n - 1) + 2 * P!A(n - 2) (for n > 2) (substituting for PA(n-1))
我们可以解析地求解 P!A 的差分方程，就像我们求解 Fibonacci 一样，注意 (-1)^n 和 2^n 都是差分方程的解，然后找到系数 a， b 这样 P!A(n) = a*2^n + b*(-1)^n.
我们最终得到等式 P!A(n) = 2^n/6 + (-1)^n/3，PA(n) 为 2^(n-1) /3 - 2(-1)^n/3.
这给了我们代码：
def PA(n):
return (pow(2, n-1) + 2*pow(-1, n-1)) / 3
for n in xrange(1, 30):
print n, PA(n)
给出输出：
1 1
2 0
3 2
4 2
5 6
6 10
7 22
8 42
9 86
10 170
11 342
12 682
13 1366
14 2730
15 5462
16 10922
17 21846
18 43690
19 87382
20 174762
21 349526
22 699050
23 1398102
24 2796202
25 5592406
26 11184810
27 22369622
28 44739242
29 89478486
我们可以用 for 循环解决这个问题，尽管 Anonymous 描述了一个封闭的形式。
function f(n){
var as = 0, abcs = 1;
for (n=n-3; n>0; n--){
as = abcs - as;
abcs *= 2;
}
return 2*(abcs - as);
}
原因如下：
Look at one strand of the decision tree (the other one is symmetrical):
A
B C...
A C
B C A B
A C A B B C A C
B C A B B C A C A C A B B C A B
Num A's Num ABC's (starting with first B on the left)
0 1
1 (1-0) 2
1 (2-1) 4
3 (4-1) 8
5 (8-3) 16
11 (16-5) 32
Cleary, we can't use the strands that end with the A's...
对于给定的三角形和更一般的图形，您可以比其他人发布的动态 programming/recursion 解决方案做得更好。每当您尝试计算（可能是有向的）图中的步数时，您都可以用传递矩阵的幂项来表示。设 M 是一个矩阵，其条目 m[i][j] 是从顶点 i 到顶点 j 的长度为 1 的路径数。对于三角形，传递矩阵是
0 1 1
1 0 1.
1 1 0
那么M^n是一个矩阵，其第i,j项是从顶点i到顶点j的长度为n的路径数。如果 A 对应于顶点 1，则需要 M^n 的 1,1 条目。
根据长度n-1的路径对长度n的路径计数进行动态规划和递归，相当于用n次乘法计算M^n，M * M * M * ... * M，这可以足够快。然而，如果你想计算 M^100，而不是做 100 次乘法，你可以使用 repeated squaring：Compute M, M^2, M^4, M^8, M^16, M^32, M ^64，然后是 M^64 * M^32 * M^4。对于较大的指数，乘法次数约为 c log_2(exponent)。
不是使用长度为 n 的路径由长度为 n-1 的路径和长度为 1 的步骤组成，而是使用长度为 n 的路径由长度为 k 的路径组成然后是一条长度为 n-k 的路径。