我的方法如下:
定义DP(l, end) = 以 end
结尾且长度为 l
的路径数量
然后 DP(l,'A') = DP(l-1, 'B') + DP(l-1,'C'),对于 DP(l,'B') 和 DP(l,'C') 同理。
对于基本情况,即 l = 1,如果结束点不是 'A',则返回0,否则返回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;
}
已编辑
回答下面的评论:
首先,DP (动态规划) 总是涉及状态。
记住,这里我们的状态是 DP(l,end),表示长度为l
且以end
结尾的路径数。因此,要使用编程实现状态,通常使用数组,因此 DP [500] [500] 只是用于存储所有可能的l
和end
的状态 DP(l,end) 的空间(这就是为什么我说如果你需要更长的长度,请更改数组大小)
但是然后你可能会问,我理解第一个维度,它是用于l
,500 意味着l
可以达到 500,但第二个维度怎么办?我只需要 'A'、'B'、'C',为什么使用 500 呢?
这里是另一个技巧(C/C++),char
类型确实可以默认作为 int
类型使用,其值等于其 ASCII
数字。当然我不记得 ASCII 表格了,但我知道大约 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' 结尾的路径数。
A B C
保持不变,只有n
会改变? - גלעד ברקן