go语言二维数组迷宫,go 二维数组

如何用C++编写一个迷宫游戏，高分求代码！！！！！！！！！！！！！

#include "graphics.h"

创新互联拥有十年成都网站建设工作经验,为各大企业提供成都做网站、成都网站建设、成都外贸网站建设服务，对于网页设计、PC网站建设（电脑版网站建设）、成都App制作、wap网站建设（手机版网站建设）、程序开发、网站优化（SEO优化）、微网站、空间域名等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了很多网站制作、网站设计、网络营销经验，集策划、开发、设计、营销、管理等网站化运作于一体，具备承接各种规模类型的网站建设项目的能力。

#include "stdio.h"

#define N 10

#define M N*N-4+1 /*堆栈最大值，用来保存路口信息*/

#define UP 1

#define DOWN -1

#define LEFT 2

#define RIGHT -2

#define UP_M man.x-1=0a[man.x-1][man.y] /*人当前位置的上一个位置*/

#define DOWN_M man.x+1Na[man.x+1][man.y]

#define LEFT_M man.y-1=0a[man.x][man.y-1]

#define RIGHT_M man.y+1Na[man.x][man.y+1]

#define ENTER 3 /*岔路的入口*/

#define HAVE 2 /*某条路已经走过*/

struct cross across,stack[M]=;

int top=1;

int PX=70,PY=40;

struct man;

/*迷宫定义，1表示路，可自行更改迷宫的路径，可使全为1，看效果等*/

int a[N][N]={0,0,0,1,1,0,1,1,1,0,

1,1,0,1,0,1,1,0,1,0,

0,1,1,1,1,0,1,1,1,1,

1,0,1,0,1,1,1,0,1,0,

1,1,1,1,0,0,1,1,1,1,

1,0,1,0,1,1,1,0,1,0,

0,0,1,1,1,0,1,1,1,0,

1,1,1,0,1,0,1,0,1,0,

0,0,1,0,1,1,1,0,1,1,

0,1,1,0,0,1,0,0,0,0};

void init_man() /*初始化人的状态，要求迷宫入口须在左侧*/

{int i;setcolor(WHITE);

for(i=0;iN;i++)

if(a[i][0]) {man.x=i;man.y=0;

if(a[i][1]) man.s=RIGHT;

else if(i+1Na[i+1][0]) man.s=DOWN;

else if(i-1=0a[i-1][0]) man.s=UP;

else

return ;}

if(i==N)

}

void show_map() /*显示迷宫*/

{int i,j;

for(i=0;iN;i++)

for(j=0;jN;j++)

if(a[i][j]) {setfillstyle(1,WHITE);

bar(PX+j*20,PY+i*20,PX+j*20+20,PY+i*20+20);}

else {setfillstyle(1,LIGHTBLUE);

bar(PX+j*20,PY+i*20,PX+j*20+20,PY+i*20+20);}

setcolor(BLACK);

for(i=0;iN;i++)

{line(PX+i*20,PY,PX+i*20,PY+20*N);

line(PX,PY+i*20,PX+20*N,PY+i*20);}

}

void show_man(int color)

{

setfillstyle(1,color);

bar(PX+man.y*20+5,PY+man.x*20+5,PX+man.y*20+20-5,PY+man.x*20+20-5);

}

int cross() /*岔路判断*/

{int count=0;

if(UP_M) count++;

if(DOWN_M) count++;

if(LEFT_M) count++;

if(RIGHT_M) count++;

return count;}

void move() /*依据人的移动状态而移动到新位置*/

{

show_man(GREEN);

switch(man.s)

{case UP:man.x-=1;break;

case DOWN:man.x+=1;break;

case LEFT:man.y-=1;break;

case RIGHT:man.y+=1;break;

}

show_man(LIGHTRED);

}

void back() /*回头走*/

{switch(man.s)

{case UP:man.s=DOWN;move();break;

case DOWN:man.s=UP;move();break;

case LEFT:man.s=RIGHT;move();break;

case RIGHT:man.s=LEFT;move();break;

}

}

void go_on() /*为通路且不是岔路时，继续向前走*/

{switch(man.s)

{case UP:if(UP_M) move();

else if(LEFT_M)

else if(RIGHT_M)

break;

case DOWN:if(DOWN_M) move();

else if(LEFT_M)

else if(RIGHT_M)

break;

case LEFT:if(LEFT_M) move();

else if(UP_M)

else if(DOWN_M)

break;

case RIGHT:if(RIGHT_M) move();

else if(UP_M)

else if(DOWN_M)

break;

}

}

int xin() /*判断人当前位置是否是新岔路口*/

{int i;

for(i=1;itop;i++)

if(man.x==stack[i].xman.y==stack[i].y) return i;

return 0;

}

void copy() /*拷贝岔路信息到across结构体*/

{across.x=man.x;

across.y=man.y;

if(UP_M==1) across.up=1;

else across.up=0;

if(DOWN_M==1) across.down=1;

else across.down=0;

if(LEFT_M==1) across.left=1;

else across.left=0;

if(RIGHT_M==1) across.right=1;

else across.right=0;

}

void rukou() /*为岔路设置一个入口*/

{switch(man.s)

{case UP:across.down=ENTER;break;

case DOWN:across.up=ENTER;break;

case LEFT:across.right=ENTER;break;

case RIGHT:across.left=ENTER;break;

}

}

void xuanlu(struct cross *p) /*在岔路时，为人选一条路行走*/

{switch(man.s)

{case UP:if(p-up==1) p-up=HAVE;

else if(p-left==1)

else if(p-right==1)

else

break;

case DOWN:if(p-down==1) p-down=HAVE;

else if(p-left==1)

else if(p-right==1)

else

break;

case LEFT:if(p-left==1) p-left=HAVE;

else if(p-up==1)

else if(p-down==1)

else

break;

case RIGHT:if(p-right==1) p-right=HAVE;

else if(p-up==1)

else if(p-down==1)

else

break;

}

}

push(struct cross *p) /*把新岔路口入栈*/

{stack[top].left=p-left;

stack[top].right=p-right;

stack[top].up=p-up;

stack[top].down=p-down;

stack[top].x=p-x;

stack[top].y=p-y;

top++;

}

int wan(struct cross *p) /*当前人所在的岔路口走完否？*/

{int count=0;

if(p-left==1) count++;

if(p-right==1) count++;

if(p-up==1) count++;

if(p-down==1) count++;

if(count0) return 0;

return 1;

}

void chukou(struct cross *p) /*人从出口出来*/

{if(p-up==ENTER) man.s=UP;

else if(p-down==ENTER) man.s=DOWN;

else if(p-left==ENTER) man.s=LEFT;

else man.s=RIGHT;

}

main()

{int c,k;

int gdriver=DETECT,gmode;

registerbgidriver(EGAVGA_driver);

initgraph(gdriver,gmode,"");

cleardevice();

show_map();

init_man();show_man(LIGHTRED);getch();delay(65000);

do{

switch(c=cross())

{case 1:switch(man.s)

{case UP:if(UP_M) move();

else back();break;

case DOWN:if(DOWN_M) move();

else back();break;

case LEFT:if(LEFT_M) move();

else back();break;

case RIGHT:if(RIGHT_M) move();

else back();break;}

break;

case 2:go_on();break;

case 3:

case 4:k=xin();

if(!k)

else {if(wan(stack[k])) chukou(stack[k]);

else xuanlu(stack[k]);}

move();

break;

}

delay(65000);

}while(!kbhit());

closegraph();}

==================================================

编译环境：tc 2.0

C++设计一个迷宫并走出来

本程序的前提是将迷宫保存在一个二维数组里，可走的地方为0，不可走的地方为1。由于采用回朔算法，不使用递归，所以首先应该建立一个栈来保存路径，路径是用一个一个点来表示的，也就是说栈中保存的是一系列点的列表。

栈节点类型说明：

struct StackNode

{

POINT Point;

struct StackNode *Next, *Prev;//双向链表形式

};

栈结构用一个类（CPointStack）实现，声明如下：

class CPointStack

{

public:

void ClearStack();//清空栈

void InitStack();//初始化栈

bool Pop(POINT pt);//弹出顶端元素，并给出该点的坐标，返回是否弹出成功

bool Push(POINT pt);//将pt点的信息压入栈，返回是否压入成功

CPointStack();

virtual ~CPointStack();

protected:

StackNode *m_psnTop;//栈顶指针

StackNode m_snBottom;//栈底，不保存点信息

};

以下为成员函数实现，都是一些数据结构的操作，应该没什么好说的：

//构造时初始化栈

CPointStack::CPointStack()

{

InitStack();

}

//析构时清空栈

CPointStack::~CPointStack()

{

ClearStack();

}

//将点压入栈(成功返回true,失败返回false)

bool CPointStack::Push(POINT pt)

{

StackNode* NewNode = new StackNode;

//是否返回true主要看这里申请内存是否成功

if(!NewNode)

return false;

NewNode-Point = pt;

NewNode-Prev = m_psnTop;

NewNode-Next = NULL;

m_psnTop-Next = NewNode;

m_psnTop = NewNode;

return true;

}

//将点弹出栈(成功返回true,栈为空则返回false)

bool CPointStack::Pop(POINT pt)

{

if(m_psnTop == m_snBottom)//是否返回true主要看这里栈是否为空

return false;

StackNode *p;

p = m_psnTop;

m_psnTop = m_psnTop-Prev;

pt = p-Point;

delete p;

m_psnTop-Next = NULL;

return true;

}

//初始化栈

void CPointStack::InitStack()

{

m_psnTop = m_snBottom;

m_snBottom.Next = NULL;

m_snBottom.Prev = NULL;

}

//清空栈

void CPointStack::ClearStack()

{

StackNode *p;

while(m_psnTop != m_snBottom)

{

p = m_psnTop;

m_psnTop = m_psnTop-Prev;

delete p;

}

}

接下来设计怎样走出这个迷宫，也就是迷宫算法的主体部分。再次用一个类实现。

在设计这个类时，我考虑到以下几点：

1、迷宫入口和出口的坐标

2、保存迷宫的2维数组

3、获得路径的函数

但是实际设计时由于没有考虑太多问题，只是以设计迷宫算法和解决一个具体迷宫为目的，所以没有考虑动态大小的迷宫，而是将迷宫大小定为601×401。而且在设计迷宫算法后没有将路径顺序输出而是直接在原图中标识（在保存迷宫数据的表中设置经过的点为2而将死路点设置为3）。

这样迷宫类（CGoMaze）的声明为：

class CGoMaze

{

public:

void Go();//寻找路径的函数

POINT m_ptIn;//入口坐标

POINT m_ptOut;//出口坐标

BYTE m_btArrMaze[401][601];//保存迷宫的二维表

CGoMaze();

virtual ~CGoMaze();

};

最后让我们来看一下CGoMaze::Go()这个函数：

我们模仿人走迷宫时的思路，设置一个当前点，一个目标点（下一个要走的点）。初始情况下当前点为入口，终止条件为当前点为出口，这样，我们的函数大概结构就出来了。

在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断，当发现任一个方向是未走过的区域时，就将当前点指向那个点进行尝试，同时将当前点入栈并做标记。而当4个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。

Go函数的具体实现如下，其实挺简单的^_^：

void CGoMaze::Go()

{

CPointStack psPath;//保存路径的栈

POINT ptCur = m_ptIn, ptNext;//设置当前点为入口

while(ptCur.x != m_ptOut.x || ptCur.y != m_ptOut.y)//判断是否已经走出

{

ptNext = ptCur;//设置目标点为当前点，便于下面偏移

if(m_btArrMaze[ptCur.y - 1][ptCur.x] == 0)

ptNext.y --;//如果上方是空的，则目标点向上偏移

else if(m_btArrMaze[ptCur.y][ptCur.x - 1] == 0)

ptNext.x --;//如果左边是空的，则目标点向左偏移

else if(m_btArrMaze[ptCur.y + 1][ptCur.x] == 0)

ptNext.y ++;//如果下方是空的，则目标点向下偏移

else if(m_btArrMaze[ptCur.y][ptCur.x + 1] == 0)

ptNext.x ++;//如果右边是空的，则目标点向右偏移

else

{//这里是没有路的状态

m_btArrMaze[ptCur.y][ptCur.x] = 3;//标记为死路

psPath.Pop(ptCur);//弹出上一次的点

continue;//继续循环

}

//如果有路的话会执行到这里

m_btArrMaze[ptCur.y][ptCur.x] = 2;//标记当前点为路径上的点

psPath.Push(ptCur);//当前点压入栈中

ptCur = ptNext;//移动当前点

}

}

其实这个部分可以将栈设置为CGoMaze类的成员，然后在Go函数里加上：

psPath.ClearStack();

这样就可以用Timer来演示走迷宫的过程了

数据结构迷宫问题（c语言）

#includestdio.h

#includestring.h

#includestdlib.h

#includetime.h

int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;

void maze()

{

int i,j;

time_t t;

srand(time(t));

for(i=0;im;i++)

for(j=0;jn;j++)

{

map[i][j]=rand()%2;

if(map[i][j])

num++;

}

if(numm*n/2)

{

for(i=0;im;i++)

for(j=0;jn;j++)

if(!map[i][j])

map[i][j]+=rand()%2;

}

map[0][0]=1;

map[m-1][n-1]=1;

}

void print()

{

int i,j;

for(i=0;im;i++)

for(j=0;jn;j++)

{

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

if(j==n-1)puts("");

}

}

void dfs(int x,int y)

{

int i,tx,ty;

if(!flag)

return;

for(i=0;i4;i++)

{

tx=x+d[0][i];

ty=y+d[1][i];

if(!f[tx][ty]tx=0ty=0txmtynmap[tx][ty])

{

f[tx][ty]=1;

a[ans]=tx;

b[ans++]=ty;

if(tx+ty==0)

{

printf("(%d,%d)\n",m,n);

for(flag=i=0;ians;i++)

printf("(%d,%d)\n",a[i]+1,b[i]+1);

return;

}

dfs(tx,ty);

f[tx][ty]=0;

ans--;

}

}

}

int main()

{

while(scanf("%d%d",m,n),m+n)

{

memset(f,0,sizeof(f));

num=ans=0;

flag=1;

maze();

print();

dfs(m-1,n-1);

if(flag)

puts("There is no path");

}

return 0;

}

高分跪求c++迷宫求解问题 （要用深度优先和广度优先两种方法）

很久以前做的，现在都忘记了。你看一下吧。我的报告，也可以发给你，不过还是期望你自己可以学会怎么做，少年智则国智。C＋＋和C一回事，你把其中的语法规则改一下就好，比如输入输出语句，将结构体改成类，也可不改，都支持的。

#include "stdio.h"

#include "conio.h" /*provide the support of getch */

#define max 10

#define maxlength (max*max) /*the max lenth of the path*/

#define zdir 4 /*the total direction*/

#include "graphics.h" /*provide the support of graphics*/

#include "dos.h" /* provide the support of function:sleep */

#include "time.h" /* provide the support of sleep */

#define M 10 /*the max lenth of the map*/

#define N 10 /*the max lenth of the map*/

/*the following four function are stating functions*/

void printmap(void);

int zfindpath(int row,int col,int erow,int ecol);

void creategraphich(int n1,int n2,int n3,int n4);

void creategraphich(int n1,int n2,int n3,int n4);

int zmap[max][max]={ {1,1,1,1,1,1,1,1,1,1},

{1,0,0,1,0,0,0,1,0,1},

{1,0,0,1,0,0,0,1,0,1},

{1,0,0,0,0,1,1,0,0,1},

{1,0,1,1,1,0,0,0,0,1},

{1,0,0,0,1,0,0,0,0,1},

{1,0,1,0,0,0,1,0,0,1},

{1,0,1,1,1,0,1,1,0,1},

{1,1,0,0,0,0,0,0,0,1},

{1,1,1,1,1,1,1,1,1,1}

};

struct {

int row,col;

}offsets[zdir]={{0,1 },

{1,0 },

{0,-1},

{-1,0}

};

struct {

int row;

int col;

} path[maxlength];

/*define a globle variable to convenience output*/

int len;

int zfindpath(int row,int col,int erow,int ecol)

{

int dir,row2,col2;

/* int x=150+col*22,y=100+row*22; */

sleep(1);

setcolor(10); /* draw a cirlce */

setfillstyle(1, 14);

circle(150+(col)*22+10,100+(row)*22+10, 8);

floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10);

if((row==erow)(col==ecol))

{ path[0].row=erow;

path[0].col=ecol; /* judge if is the exit */

return 1;

} /* the end of if */

zmap[row][col]=2; /* block current position */

for(dir=0;dirzdir;dir++)

{

row2=row+offsets[dir].row; /* step to next space */

col2=col+offsets[dir].col;

if(zmap[row2][col2]==0) /* mean the way could go at this stage */

{

len=zfindpath(row2,col2,erow,ecol);

if(len0)

{

path[len].row=row2; /* use recursion to find the path */

path[len].col=col2;

return ++len;

} /*the end of if */

} /*the end of if */

} /* the end of for */

sleep(1);

setfillstyle(1, 15);

bar( 150+col*22,100+row*22,170+col*22,120+row*22);

/* sleep(1); */

return 0;

} /* the end of zfindpaht */

void printmap() /* first ,print the map that we will go */

{

int i,j;

for(i=0;imax;i++)

{

for(j=0;jmax;j++)

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

printf("\n");

}

getch();

}

void createmap(int n1,int n2,int n3,int n4)

{

int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;

void *buf;

int gdriver=DETECT,gmode=VGAHI;

initgraph(gdriver,gmode,"c:\\tc");

cleardevice();

setbkcolor(10);

setcolor(1);

settextstyle(4, 0, 5);

outtextxy(70,20,"hello,welcome to here! ");

setcolor(4);

setfillstyle(1, 4);

for(i=0;i10;i++)

for(j=0;j10;j++)

{

if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}

else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}

}

line(100,80,150+n2*22,100+n1*22); /* draw a line */

line(337+(n4-8)*22,287+(n3-8)*22,337,360);

setcolor(1);

settextstyle(4, 0, 3);

outtextxy(80,60,"this is the entrance! ");

outtextxy(320,360,"this is the exit! ");

}

void creategraphich(int n1,int n2,int n3,int n4)

{

int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;

void *buf;

int gdriver=DETECT,gmode=VGAHI;

initgraph(gdriver,gmode,"c:\\tc");

cleardevice();

setbkcolor(10);

setcolor(1);

settextstyle(4, 0, 5);

outtextxy(70,20,"hello,welcome to here! ");

setcolor(4);

setfillstyle(1, 4);

for(i=0;i10;i++)

for(j=0;j10;j++)

{

if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}

else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}

}

line(100,80,150+n2*22,100+n1*22); /* draw a line */

line(337+(n4-8)*22,287+(n3-8)*22,337,360);

setcolor(1);

settextstyle(4, 0, 3);

outtextxy(80,60,"this is the entrance! ");

outtextxy(320,360,"this is the exit! ");

setcolor(4); /* draw a circle heart */

setfillstyle(1, 4);

sector(250,350,0,180,20,20); /* draw the upper circle */

sector(290,350,0,180,20,20); /* draw the downer circle */

sector(310,350,180,240,80,76);

sector(230,350,300,360,80,76);

setcolor(10); /* draw a cirlce */

setfillstyle(1, 14);

circle(150+(n2)*22+10,100+(n1)*22+10, 8);

floodfill(150+(n2)*22+10+4, 100+(n1)*22+10+4, 10);

size=imagesize(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8);

buf=malloc(size);

getimage(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8,buf);

/*sleep(2);

putimage(192,122 , buf, COPY_PUT); */

for(i=len;i0;i--) /* the total number of the path is len-1 */

{

trow=path[i-1].row-path[i].row;

tcol=path[i-1].col-path[i].col;

sleep(1);

x=x+tcol*22;

y=y+trow*22;

putimage(x,y, buf, COPY_PUT);

}

/* printf the result*/

setcolor(1);

settextstyle(4, 0, 3);

outtextxy(357,287,"sussessfully!!!");

getch();

closegraph();

free((void *)buf);

}

void changemap(int d)

{

FILE *fw;

int i,j;

if(d==1)

{

fw=fopen("c:\\tc\\a.txt","r");

if(!fw) {printf("not found!"); getch();return;}

for(i=0;iM;i++)

{ for( j=0;jN;j++ ) { fscanf(fw,"%d",zmap[i][j]);}

} /* the end of for */

}/* the end of first if*/

else {

fw=fopen("c:\\tc\\b.txt","r");

if(!fw) {printf("not found!"); getch();return;}

for(i=0;iM;i++)

{ for( j=0;jN;j++ ) { fscanf(fw,"%d",zmap[i][j]);}

} /* the end of for */

} /* the end of else */

printf("the map we will follow to search :\n");

for(i=0;iM;i++)

{ for(j=0;jN;j++) { printf(" %d",zmap[i][j]);}

printf("\n");

}

getch();

fclose(fw);

}

main()

{

while(1){

int i,j,n1,n2,n3,n4,n5,n6;

int zch;

/* while(1){ */

len=0;

printf("if you want to use the default map,press 1,if you want to use the spare map,press 2 :\n");

scanf("%d",zch);

if(zch==2)

changemap(1);

/*printmap(); */

else

{

changemap(2);

/* printmap(); */ /* first ,print the map that we will go */

}

printf("please input the startpoint(row,col):\n"); /* input the start point and end point ,those two value should less then 10 and larger then 0*/

scanf("%d%d",n1,n2);

printf("please input the endpoint(row,col):\n");

scanf("%d%d",n3,n4);

n5=n1;

n6=n2;

createmap(n5,n6,n3,n4); /* in this step ,we will create the primitive map */

zfindpath(n1,n2,n3,n4); /* function of searching the path */

path[len].row=n5;

path[len].col=n6;

getch();

closegraph();

printf("the resultant path is \n");

for(i=len;i0;i--)

{

printf("(%d,%d)\n",path[i].row,path[i].col);

} /* the end of for*/

getch();

printf("now,we will create the final graphics of the map:\n"); /* create the final graphics of the map*/

getch();

creategraphich(n5,n6,n3,n4);

} /* the end of while */

} /* the end of main */

关于n个数里选k个的不同方法及一些思考

给出两个整数n和k，返回从1到n中取k个数字的所有可能的组合

例如：

如果n=4，k=2，结果为

[↵ [2,4],↵ [3,4],↵ [2,3],↵ [1,2],↵ [1,3],↵ [1,4],↵]

这题本身并不是特别的难,但是不同方法的复杂度差很多,而且响应了之前碰到的那句:

最先想到的方式:

方法一:

用走迷宫的思路暴力递归,n个数每一个都可以看做迷宫的一步,有选和不选两种选择:

这种方式表面上像一颗二叉树一样展开n个数有2^n次方种递归,但是对二叉树进行适当裁剪,对不要对枝叶不再扩展,勉强通过了测试55 ms 42.3 MB;

方法二:

层序递归的思路,一层层的去求,求f(n,1),f(n,2),......,f(n,k)----n个数选1个的集合,选2个的集合....k个的集合;这种方式会建立大量的集合;

一开始我这样做,0-k的每一位上有1-n种选择,表面上感觉是k*n的复杂度,但是由于是不重复的,每次为了避免前面选过的数再次被选我用的HashSet不断判断的方式来避免重复加入,最后直接超时了;

方法三:

动态规划的背包思路: dp[i][j]---∑dp[i-1][j]+∑f(dp[i-1][j-1],i);利用前面的结果,二维的一格格的求,(方法二相当于一维的f(n,1)-f(n,2)-f(n,3)-.....-f(n,k),n恒定,一层层的求), 这种方式比方法二快,但比走迷宫暴力并剪枝的方式慢4倍, 213 ms -270.3 MB勉强通过;

( 之前华为那道题两个数组互相交换,最后最小值,那道题则用动态规划转为背包问题最好,映证了那句话:求所有符合的结果用深度递归(及时修剪),求最优结果或结果数量用动态规划; )

方法四:

用DFS深度优先遍历,类似于走迷宫但是每一步横向铺开,方法一的每一步都只考虑两种情况,选和不选,这里直接扩散到 i到n-(k-size)+1 (其中size是前面递归过来的已经选了的情况数;

)中的任意位置,类似于棋盘不只上下左右走了,棋子♟可以跳到任意位置;

在每一次递归前list.add(i),执行go(next)递归之后,又及时的进行删除动作,list.remove(last);只在最后符合要求时clone这个list,并放入结果集合;(不保存中间结果)

最后只用了2ms 42MB;