dp初见?

#include<bits/stdc++.h>
using namespace std;

long long int map1[40][40];
int map2[40][40];
int mx,my,endx,endy;

int step1[8][2]={{1,2},{2,1},{-1,2},{2,-1},{-2,1},{1,-2},{-1,-2},{-2,-1}};
void stepm(int a,int b);
int main()
{
    cin>>endx>>endy>>mx>>my;
    
    endx += 2;
    endy += 2;
    mx += 2;
    my += 2;
    map2[mx][my]=1;
    stepm(mx,my);
    int i,j;
    
    map1[2][1] = 1;
    for(i = 2;i <= endx;i++)
    {
        for(j = 2;j <= endy;j++)
    {
        if(map2[i][j]==1)
            continue;    
        
        map1[i][j]=map1[i-1][j]+map1[i][j-1];
    }

    }
    
    cout<<map1[endx][endy];
//    printf("%lld",map1[endx][endy]);    
}

void stepm(int a,int b)
{
    int i;
    int nx,ny;
    
    for(i = 0;i <= 7;i++)
    {
        nx = a + step1[i][0];
        ny = b + step1[i][1];
        if(nx <= endx && nx>=0 && ny<= endy && ny >=0 && (nx != 0 || ny !=0)&&(nx!=endx ||ny != endy))
            map2[nx][ny] = 1;
    }
    
}

过河卒,比较经典的一道dp题,第一次思路没对,超时,用的dfs,感觉还是有些过于执着写模板,希望能早点改一下这种习惯。

上一篇:算法中的字符串问题 字符串匹配


下一篇:AcWing 40. 顺时针打印矩阵(C++)- 模拟、vector