给定一个数字字符串,我想找到将该字符串分解为小于26的单个数字的方法数。
例如,"8888888"只能被分解为"8 8 8 8 8 8 8"。而"1234567"可以被分解为"1 2 3 4 5 6 7"、"12 3 4 5 6 7"和"1 23 4 5 6 7"。
我想要一个递归关系的解决方案,并且需要使用动态规划的代码。
这是我目前得到的内容。它仅涵盖了基本情况,即空字符串应返回1,一个数字字符串应返回1,所有数字都大于2的字符串应返回1。
例如,"8888888"只能被分解为"8 8 8 8 8 8 8"。而"1234567"可以被分解为"1 2 3 4 5 6 7"、"12 3 4 5 6 7"和"1 23 4 5 6 7"。
我想要一个递归关系的解决方案,并且需要使用动态规划的代码。
这是我目前得到的内容。它仅涵盖了基本情况,即空字符串应返回1,一个数字字符串应返回1,所有数字都大于2的字符串应返回1。
int countPerms(vector<int> number, int currentPermCount)
{
vector< vector<int> > permsOfNumber;
vector<int> working;
int totalPerms=0, size=number.size();
bool areAllOverTwo=true, forLoop = true;
if (number.size() <=1)
{
//TODO: print out permetations
return 1;
}
for (int i = 0; i < number.size()-1; i++) //minus one here because we dont care what the last digit is if all of them before it are over 2 then there is only one way to decode them
{
if (number.at(i) <= 2)
{
areAllOverTwo = false;
}
}
if (areAllOverTwo) //if all the nubmers are over 2 then there is only one possable combination 3456676546 has only one combination.
{
permsOfNumber.push_back(number);
//TODO: write function to print out the permetions
return 1;
}
do
{
//TODO find all the peremtions here
} while (forLoop);
return totalPerms;
}
0
开头吗?(因此101
可以是1 0 1
,10 1
或1 01
吗?) - Jarod42