关于递归思考问题的启发

动态规划是一种编程技巧【优化】而不是算法，对于动态规划来说，最基础的就是递归式分解问题。

所以，学会动态规划的第一步，是学会分解问题。

例题：旋转打印矩阵，给你一个矩阵，要求将矩阵内元素旋转打印：

即： 1 2 3 4

5 6 7 8

9 10 11 12

打印结果为1 2 3 4 8 12 11 10 9 5 6 7。

方法1：用坐标指针进行顺时针遍历的同时进行打印，需要有的参数是一个bool类型的矩阵表示这个点是否已被访问过或者是否是边界。

方法2：我们注意到，任何矩阵都可以按照矩形框来分解。而我们需要的参量，就是他的左上端点和右下端点，用以防止越界遍历。

于是这题的解法有了，我们需要设计一个printEdge函数，给两个点的坐标，顺时针打印出以这两个点为端点构成的矩形的边框元素。

代码：

#include<cstdio>
using namespace std;
int Array[100][100];

void printEdge(int lx,int ly,int rx,int ry){
   if(lx==rx){//临界打印条件竖直线
       for(int j=ly;j<=ry;j++){
           printf("%d ",Array[lx][j]);
       }
   }else if(ly==ry){//水平线
       for(int j=lx;j<=rx;j++){
           printf("%d ",Array[j][ly]);
       }
   }else{
       int curx=lx;
       int cury=ly;
       while(cury!=ry){
           printf("%d ",Array[curx][cury++]);
       }
       while(curx!=rx){
           printf("%d ",Array[curx++][cury]);
       }
       while(cury!=ly){
           printf("%d ",Array[curx][cury--]);
       }
       while(curx!=lx){
           printf("%d ",Array[curx--][cury]);
       }
   }
}

int main(){
   int n,stl=1,str=1,ovl,ovr;
   scanf("%d",&n);
   ovl=ovr=n;
   for(register int i=1;i<=n;i++){
       for(register int j=1;j<=n;j++){
           scanf("%d",&Array[i][j]);
       }
   }
   while(stl<=ovl&&str<=ovr){
       printEdge(stl++,str++,ovl--,ovr--);
   }
}

变：将正方形旋转90°，打印结果，要求O(1)空间复杂度。

思考：如果空间上不约束，可以将元素用上述方法读，然后填入辅助矩阵，或者可以将上述元素读进string，旋转的结果只是在回填的时候给这个string增加了偏移量而已。举例说明，上例矩阵用string存储读取外层矩形框，1 2 3 4 8 12 11 10 9 5 ，旋转90°只是从9开始填这个框而已。

空间上约束：其实上述的string只是一个变量，理论上说已经算O(1)的复杂度了，不过这里给出另一个更好的实现。

1.分解问题：我们还是将正方形按照框分解，把每个外框旋转对了，正方形就转好了。

2.如何不用string旋转框呢？我们以上个例子的矩阵最外框为例，按照旋转后的对应位置将框的元素分组，也就是，1->4->12->9为一组，一共可以分三组【也就是左上和右下坐标的横或纵坐标差】

那么我们把为同一组的元素抽象，A(lx,ly+i)->A(lx+i,ry)->A(rx,ry-i)->A(rx-i,ly)，于是核心实现变成了四个变量交换：

#include<cstdio>
using namespace std;
int A[100][100];
void rotateEdge(int lx,int ly,int rx,int ry){
   int len=rx-lx,temp;
   for(int i=0;i<len;i++){
       temp=A[lx][ly+i];
       A[lx][ly+i]=A[rx-i][ly];//4->1
       A[rx-i][ly]=A[rx][ry-i];//3->4
       A[rx][ry-i]=A[lx+i][ry];//2->3
       A[lx+i][ry]=temp;//1->2
   }
}

int main(){
   int n,lx,ly,rx,ry;
   scanf("%d",&n);
   for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
           scanf("%d",&A[i][j]);
       }
   }
   lx=ly=1;
   rx=ry=n;
   while(lx<rx){
       rotateEdge(lx++,ly++,rx--,ry--);
   }
   for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
           printf("%d ",A[i][j]);
       }
       printf("\n");
   }
   return 0;
}

例题2：“之”字形打印矩阵，打印方式去下图：

关于递归思考问题的启发

切忌被题目迷惑，嘴上说是之形打印，其实就是按照斜线将矩阵分层输出罢了。给定上顶点和下顶点，由于这里的斜线都是斜率为1的，我们可以得到所有的点，只要交替着从上向下到从下到上即可。

解题方法：实现一个函数，给定上下端点，根据一个Bool值选择从上至下还是从下至上。

#include<cstdio>
#include<algorithm>
using namespace std;
int A[100][100];

void printLine(int ux,int uy,int dx,int dy,int flag){
   int sx,sy;
   if(flag){//下到上
       sx=dx,sy=dy;
       while(sx>=ux){
           printf("%d ",A[sx][sy]);
           sx--;
           sy++;
       }
   }else{
       sx=ux,sy=uy;
       while(sx<=dx){
           printf("%d ",A[sx][sy]);
           sx++;
           sy--;
       }
   }
}

int main(){
   int m,n,ux,uy,dx,dy;
   bool flag=true;
   scanf("%d%d",&m,&n);
   for(int i=1;i<=m;i++){
       for(int j=1;j<=n;j++){
           scanf("%d",&A[i][j]);
       }
   }
   ux=uy=1;
   dx=dy=1;
   while(ux!=m){
       printLine(ux,uy,dx,dy,flag);
       flag=!flag;
       ux=uy==n?ux+1:ux;//看上端点有没有到右端
       uy=uy==n?uy:uy+1;
       dy=dx==m?dy+1:dy;//看下端点有没有到底端
       dx=dx==m?dx:dx+1;
   }
   printf("%d",A[m][n]);
   return 0;
}

关于递归思考问题的启发

相关推荐