爬楼梯问题--有n阶台阶,上楼可以一步上1阶,2阶,3阶,计算共有多少种不同的走法

简单的dp问题：

#include

int step[2048];

int p = step;

void foo(int n)

{

if(n > 0) {

if(n > 1) {

p++ = 2;

foo(n-2);

--p;

}

p++ = 1;

foo(n-1);

--p;

} else {

for(int k = step; k != p; ++k)

printf("%d ",k);

putchar('\n');

}

}

int main()

{

foo(5);

}

你可能被题目给出的例子给误导了。题目给出的例子：

4

2 3 5 10

也就是：(2，3) (3，5) (5，10) (10，2)，最优解刚好是按顺序的，也就是

4和1，炼出的珠子再和2，接着再和3。

因此，你的程序找最优解的算法，就是枚举从任意一颗珠子开始，一直按一个方向炼制下去。

因为有N个珠子，因此有N中结果，你就从这个N个结果中找一个最大的，作为最优值。

但是，这个算法是不完整的！！！题目并没说一定要按给出顺序，一直炼制下去！你可以任意挑出两个珠子，只要它们的头和尾一样就可以炼制了。

因此实际的炼制方法，远远多于N。设N颗珠子有F(N)种炼制方法，则：

F(N)=NF(N-1)，N>=3。且 F(1)=0，F(2)=1。

可以统一成：F(N)=N!/2，N>=2。F(1)=0。

题目的N范围：（4<=N<=100），如果采用暴力枚举的话，F(N)会达到很大的数量级。

你要问的，为什么：

7

23 17 212 113 71 301 33

正确结果：31182687

而我代码所产生的结果是：17489304

就是因为你枚举了N=7种情况，实际有7!/2=2520种情况，远远大于你枚举的范围。

通过上面的分析，可以知道，暴力枚举是行不通的。这题就是要用你提到的DP（动态规划来做的）。

用DP（动态规划）的做法是：

1)设有 N 颗珠子，信息保存在 pearls[N]中

2)energy[i][j] 表示从第 i 颗珠子到第 j 颗珠子能获得的最大能量，

初始设置为-1，表示还没有计算出来。

3)当 i==j ，是同一颗珠子，energy[i][j]=0

当 (i+1)%N==j，表示的是两颗相邻的珠子，能获得能量为：

energy[i][j] = pearls[i]pearls[(i+1)%N]pearls[(i+2)%N]

其他情况，在 i,j 之间任意选一个位置 k(i<=k<j)断开，计算：

a) 第 i 颗珠子到第 k 颗珠子的最大能量：energy[i,k]，

也就是第 k 颗珠子左边所有珠子的最大能量;

b) 第 k+1 颗珠子到第 j 颗珠子的最大能量：energy[k+1,j]，

也就是第 k 颗珠子右边所有珠子的最大能量;

c) 第k可珠子左边和右边计算能量后，各剩下一颗珠子，这两颗珠子获得的能量为：

pearls[i]pearls[k]pearls[(j+1)%N]

a,b,c三部分的能量相加，就是当选择 k 位置断开后，在珠子 i,j直接能获得的最大能量。

如果这个能量比原来的 energy[i][j] 要大，energy[i][j] 就更新为这个能量值。

4) energy[0][N-1]就是题目要求的，使用N颗珠子能获得的最大能量。

用dp的方法，并在每一步记录一下是哪一步转移过来的

倒着找回去就可以了

用C++写了一发，有少许注释，供参考

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#define MAX(a,b) ((a)>(b)(a):(b));

using namespace std;

struct Point{

int x,y;

Point(int x=0,int y=0):x(x),y(y){}

};

//

//the operator 

struct Operator{

int type;

int to;

Operator(int type=0,int to=0):type(type),to(to){}

/

type    0    No Opeartor

1    Insert to

2    Delete

3    Change ->to 

/

};

//

//new and delete for 2D array

template<class T>

T new_2D_Array(int n,int m){

T res=new T[n];

res[0]=new T[nm];

for(int i=1;i<n;i++)

    res[i]=res[i-1]+m;

return res;

}

template<class T>

void delete_2D_Array(T src){

delete []src[0];

delete []src;

}

//

int get_eu(char i,char j){

    return i==j  0:1;

}

/  dp for min edit distance  /

/  pre means witch status transfor to current status  /

/  op means how to change from pre to current/

int min_Edit_Dis(string s1,string s2,string &res,vector<Operator>&resop,vector<int>&respos){

int ret=0,reti=-1,retj=-1,n=s1size(),m=s2size();

int dp=new_2D_Array<int>(s1size()+1,s2size()+1);

Point pre=new_2D_Array<Point>(s1size()+1,s2size()+1);

Operator op=new_2D_Array<Operator>(s1size()+1,s2size()+1);

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

dp[i][j]=0;

pre[i][j]=Point(-1,-1);

}

}

    dp[0][0]=0;

    op[0][0]=Operator(0,'!');

for(int i=1;i<=n;i++){

dp[i][0]=i;

    op[i][0]=Operator(2,64);

    pre[i][0]=Point(i-1,0);

}

for(int i=1;i<=m;i++){

dp[0][i]=i;

op[0][i]=Operator(1,s2[i-1]);

pre[0][i]=Point(0,i-1);

}

pre[0][0]=Point(-1,-1);

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

dp[i][j]=dp[i-1][j]+1;

pre[i][j]=Point(i-1,j);

op[i][j]=Operator(2,64);

if(dp[i][j-1]+1<dp[i][j]){

dp[i][j]=dp[i][j-1]+1;

pre[i][j]=Point(i,j-1);

op[i][j]=Operator(1,s2[j-1]);

}

if(dp[i-1][j-1]+get_eu(s1[i-1],s2[j-1])<dp[i][j]){

dp[i][j]=dp[i-1][j-1]+get_eu(s1[i-1],s2[j-1]);

pre[i][j]=Point(i-1,j-1);

if(s1[i-1]==s2[j-1])

op[i][j]=Operator(0,'!');

else

op[i][j]=Operator(3,s2[j-1]);

}

}

}

     

    ret=dp[n][m];

/   print pre op dp

    printf("(%d,%d)\n",reti,retj);

printf(" ");

for(int i=0;i<=m;i++)

if(i==0) printf("         ");

    else printf("%5c    ",s2[i-1]);

printf("\n");

for(int i=0;i<=n;i++){

if(i==0) printf(" ");

else printf("%c",s1[i-1]);

for(int j=0;j<=m;j++){

printf(" (%2d,%2d) ",pre[i][j]x,pre[i][j]y);

}

cout<<endl;

}

printf("(%d,%d)\n",reti,retj);

printf(" ");

for(int i=0;i<=m;i++)

if(i==0) printf("         ");

    else printf("%5c    ",s2[i-1]);

printf("\n");

for(int i=0;i<=n;i++){

if(i==0) printf(" ");

else printf("%c",s1[i-1]);

for(int j=0;j<=m;j++){

printf(" (%2d,%2c) ",op[i][j]type,op[i][j]to);

}

cout<<endl;

}

    printf("  ");

for(int i=0;i<=m;i++) 

if(i==0) printf("    ");

    else printf("%c  ",s2[i-1]);

printf("\n");

for(int i=0;i<=n;i++){

if(i==0) printf("  ");

else printf("%c ",s1[i-1]);

for(int j=0;j<=m;j++){

printf("%2d ",dp[i][j]);

}

cout<<endl;

}

/

resopclear();

resposclear();

int curi=n,curj=m;  

/to get the road (include null op)/

while(curi!=-1){

resoppush_back(op[curi][curj]);

respospush_back(curi-1);

int tmpi=pre[curi][curj]x;

curj=pre[curi][curj]y;

curi=tmpi;

}

return ret;

}

/delete the null op,and get the string of each step/

/Skill:

    Change Form Right to Left,so the index will not change when operator

/

void get_Recoder(string src,vector<Operator>&op,vector<int>&pos,vector<string>&res){

    resclear();

    respush_back(src);

    vector<Operator> tmpop;

    vector<int> tmppos;

    tmpopclear();

    tmpposclear();

    string curs=src;

    char buffer[2]={0,0};

for(int i=0;i<opsize();i++){

Operator curp=op[i];

int curpos=pos[i];

if(curptype==0) continue;

else if(curptype==1){

curs=cursinsert(curpos+1,1,curpto);

respush_back(curs);

}

else if(curptype==2){

curs=curserase(curpos,1);

respush_back(curs);

}

else if(curptype==3){

curs[curpos]=curpto;

respush_back(curs);

}

tmppospush_back(curpos);

tmpoppush_back(curp);

}

opclear();

posclear();

for(int i=0;i<tmppossize();i++){

oppush_back(tmpop[i]);

pospush_back(tmppos[i]);

}

}

/Print the process/

void printRecord(string src,vector<Operator>&op,vector<int>&pos,vector<string>&road){

char operatorList[4][15]={"   GOAL   ","  INSERT  ","  DELETE  ","  CHANGE  "};

int spacesize=6;

for(int i=0;i<roadsize();i++)

spacesize=MAX(spacesize,road[i]size());

for(int i=0;i<spacesize+32;i++)

printf("_");

/

Pos:

k i t t e n

0 1 2 3 4 5 6

/

printf("\n|%-s | pos | operator | form | to |\n|",spacesize,"string");

for(int i=0;i<spacesize;i++)printf("-");

printf("------------------------------|\n");

printf("|%-s |   / |  SOURCE  |  /   | /  |\n",spacesize,srcc_str());

for(int i=0;i<opsize();i++){

string tmps=road[i];

Operator top=op[i];

int tpos=pos[i];

printf("|%-s |%4d |%s|  %c   | %c  |\n",spacesize,tmpsc_str(),tpos+(toptype==1  1:0),operatorList[toptype],(toptype==3 || toptype==2)  src[tpos]:'/',(toptype==3 || toptype==1) topto:('/'));

}

printf("|%-s |   / |  TARGET  |  /   | /  |\n",spacesize,road[roadsize()-1]c_str());

for(int i=0;i<spacesize+32;i++)printf("-");

printf("\nRoad Finished\n");

}

int main(){

string A="kitten";

string B="sitting";

string C;

vector<Operator>op;

vector<int>pos;

vector<string>road;

int res=min_Edit_Dis(A,B,C,op,pos);

printf("The min edit dis is: %d\n",res);

get_Recoder(A,op,pos,road);

printRecord(A,op,pos,road);

return 0;

}

以上就是关于爬楼梯问题--有n阶台阶,上楼可以一步上1阶,2阶,3阶,计算共有多少种不同的走法全部的内容，包括:爬楼梯问题--有n阶台阶,上楼可以一步上1阶,2阶,3阶,计算共有多少种不同的走法、NOIP2006提高组题：能量项链，求大神指出我的代码逻辑错误、最小编辑距离算法 怎么得到路径等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！