f*********m
发帖数: 726 | 1 给一个count and say的结果，确定有多少种可能的输入。比如，"1211" 可以解释成1
个2，1个1，121个1,12个11或者121个1。所以有四种可能的输入。
这个题是glassdoor上看到的，当时作者只是给了2，1个1，121个1这两个例子。
我有个backtracking的想法。
int numberOfWays(string& s, int index)
{
if (index == s.size())
return 1;
int num = 0;
for (int i = index; i < size(); ++i)
{
for (int j = i+1; j < size(); ++j)
{
if (s.substr(index, i) can be the count && s.substr(i+1, j) can
be the number)
num += numberOfWays(s, j+1);
}
}
return num;
}
不知道对不对，或者大家有没有更好的方法？
谢谢。 |
f*********m
发帖数: 726 | |
l*****a
发帖数: 14598 | 3 1个211,12个11可以吗
1
【在 f*********m 的大作中提到】
: 给一个count and say的结果，确定有多少种可能的输入。比如，"1211" 可以解释成1
: 个2，1个1，121个1,12个11或者121个1。所以有四种可能的输入。
: 这个题是glassdoor上看到的，当时作者只是给了2，1个1，121个1这两个例子。
: 我有个backtracking的想法。
: int numberOfWays(string& s, int index)
: {
: if (index == s.size())
: return 1;
:
: int num = 0;
|
r**h
发帖数: 1288 | 4 题意没理解错的话，应该是count数字字符吧？前面数字可以任意位，最后字符只能1位
我想到的是二维DP：
DP[1][i] = 0;（不能空余第一个单字）
DP[i][N-1] = 0;
子段长度不大于3的情况，不能分离成两个子段
DP[i][i] = 0;
DP[i][i+1] = 1;
DP[i][i+2] = 1;
子段长度大于3的情况，可能的组合数
j>=i+3
DP[i][j] = sum(DP[i][k] * DP[k+1][j])+1 (i
不知道是否正确，求指点
1
【在 f*********m 的大作中提到】
: 给一个count and say的结果，确定有多少种可能的输入。比如，"1211" 可以解释成1
: 个2，1个1，121个1,12个11或者121个1。所以有四种可能的输入。
: 这个题是glassdoor上看到的，当时作者只是给了2，1个1，121个1这两个例子。
: 我有个backtracking的想法。
: int numberOfWays(string& s, int index)
: {
: if (index == s.size())
: return 1;
:
: int num = 0;
|
b*****n
发帖数: 618 | 5 一维DP就可以吧
【在 r**h 的大作中提到】
: 题意没理解错的话，应该是count数字字符吧？前面数字可以任意位，最后字符只能1位
: 我想到的是二维DP：
: DP[1][i] = 0;（不能空余第一个单字）
: DP[i][N-1] = 0;
: 子段长度不大于3的情况，不能分离成两个子段
: DP[i][i] = 0;
: DP[i][i+1] = 1;
: DP[i][i+2] = 1;
: 子段长度大于3的情况，可能的组合数
: j>=i+3
|
f*********m
发帖数: 726 | 6 请展开说说。
【在 b*****n 的大作中提到】
: 一维DP就可以吧
|
f*********m
发帖数: 726 | 7 应该也可以。
【在 l*****a 的大作中提到】
: 1个211,12个11可以吗
:
: 1
|
f*********m
发帖数: 726 | 8 为什么最后字符只能是一位呢？
可能我把题说得不清楚，改正了。
【在 r**h 的大作中提到】
: 题意没理解错的话，应该是count数字字符吧？前面数字可以任意位，最后字符只能1位
: 我想到的是二维DP：
: DP[1][i] = 0;（不能空余第一个单字）
: DP[i][N-1] = 0;
: 子段长度不大于3的情况，不能分离成两个子段
: DP[i][i] = 0;
: DP[i][i+1] = 1;
: DP[i][i+2] = 1;
: 子段长度大于3的情况，可能的组合数
: j>=i+3
|
b*****n
发帖数: 618 | 9 需要处理开头是0的情况吗？
比如011这种可以算做01个1或者0个11吗？
还有101这种可以算1个01吗？
简单一点，如果不考虑上述情况
DP[0] = 1
DP[1] = 0
DP[i] = sum (DP[k]* (i-k-1)) where (0<=k<=i-2)
如果需要考虑上面开头是0的情况的话，需要在DP的时候处理一下
【在 b*****n 的大作中提到】
: 一维DP就可以吧
|
