动态规划学习——机器人运动

//一共有N个位置，机器人从start开始，走K步到end
//机器人到1后只能向2运动，到N后只能向N-1运动，即不能越界，只能在1-N的位置运动
//求总的路线的个数
//例：
//N=4,startp=1,endp=3,K=4
//则路线如下：
//1->2->3->4->3
//1->2->3->2->3
//1->2->1->2->3
//总共有3条路线

#include<iostream>
using namespace std;
int N,K,startp,endp;
int ways2_temp[10000][10000]={0};
int ways3_temp[10000][10000]={0};

void ways2_initial()
{
    int i,j;
    for(i=0;i<N+1;i++)
        for(j=0;j<K+1;j++)
            ways2_temp[i][j]=-1;
}

void ways3_initial()
{
    int i,j;
    for(i=0;i<N+1;i++)
        for(j=0;j<K+1;j++)
            ways3_temp[i][j]=0;
}

//法一：递归
//N为位置数，rest为剩余步数，cur为当前位置，endp为目标位置
int process1(int N,int rest,int cur,int endp)
{
    if(rest==0) return cur==endp?1:0;  //rest等于0时应该返回，此时应检查cur是否等于endp，若相等，则返回1（这条路可以走），否则返回0（此路不通）
    if(cur==1) return process1(N,rest-1,2,endp);//若cur=1，则路线数等于cur=2,rest=rest-1时的路线数
    if(cur==N) return process1(N,rest-1,N-1,endp);//若cur=N，则路线数等于cur=N-1,rest=rest-1时的路线数
    //如果cur不等于1，也不等于N，即在中间位置，则下一步既可以向左走，又可以向右走，所以等于左右步数相加
    else return process1(N,rest-1,cur+1,endp)+process1(N,rest-1,cur-1,endp);
}

//法二：带有缓存的解决办法
//首先判断是否已经缓存了(cur,rest)的值（即路线数），若有则直接返回
//若没有则开始递推，且在返回结果前将结果保存到缓存数组中
int process2(int N,int rest,int cur,int endp)
{
    if(ways2_temp[cur][rest]!=-1) return ways2_temp[cur][rest];
    int cnt=0;
    if(rest==0) cnt=(cur==endp?1:0);  //rest等于0时应该返回，此时应检查cur是否等于endp，若相等，则返回1（这条路可以走），否则返回0（此路不通）
    else if(cur==1) cnt=process2(N,rest-1,2,endp);//若cur=1，则路线数等于cur=2,rest=rest-1时的路线数
    else if(cur==N) cnt=process2(N,rest-1,N-1,endp);//若cur=N，则路线数等于cur=N-1,rest=rest-1时的路线数
    //如果cur不等于1，也不等于N，即在中间位置，则下一步既可以向左走，又可以向右走，所以等于左右步数相加
    else cnt=process2(N,rest-1,cur+1,endp)+process2(N,rest-1,cur-1,endp);
    ways2_temp[cur][rest]=cnt;
    return cnt;
}

//法三：动态规划
//由前面的方法可知，可以构建一个数组，行数为N,列数为K+1，第i行第j列的数值表示当前位置为i剩余步数为j时的路线总数
//而对于二维数组中每个值，都等于左上和右下值之和（第一行只有右下，最后一行只有左上）
//此外，对于第一列，即剩余步数rest=0时，只有当行数等于目标位置endp时，值为1
//故可以从左到右扫描数列，填充二维数组，最后的结果为第endp行第K列的值
int process3(int N,int K,int startp,int endp)
{
    int i,j;
    for(i=0;i<=K;i++) ways3_temp[i][0]=0;
    ways3_temp[endp][0]=1;
    for(i=1;i<=K;i++){
        ways3_temp[1][i]=ways3_temp[2][i-1];
        for(j=1;j<=N;j++){
            ways3_temp[j][i]=ways3_temp[j-1][i-1]+ways3_temp[j+1][i-1];
        }
        ways3_temp[N][i]=ways3_temp[N-1][i-1];
    }
    return ways3_temp[startp][K];
}


int main()
{
    int choice;
    do
    {
        cout<<"请输入位置总数N:   ";
        cin>>N;
        cout<<"请输入开始位置startp:   ";
        cin>>startp;
        cout<<"请输入结束位置endp:   ";
        cin>>endp;
        cout<<"请输入一共要走的步数K:   ";
        cin>>K;
        int result1=process1(N,K,startp,endp);
        cout<<"法一 直接递归 得出 一共有 "<<result1<<" 种走法"<<endl;
        ways2_initial();
        int result2=process2(N,K,startp,endp);
        cout<<"法二 缓存递归 得出 一共有 "<<result2<<" 种走法"<<endl;
        ways3_initial();
        int result3=process3(N,K,startp,endp);
        cout<<"法三 动态规划 得出 一共有 "<<result3<<" 种走法"<<endl;
        cout<<"是否继续?继续输入1"<<endl;
        cin>>choice;
    }while(choice==1);

    return 0;
}

参考资料：

bilibili 马士兵教育——左程云

【应B友要求火速上线！算法大神（左程云）教你从暴力递归到动态规划，吊打所有暴力递归、动态规划问题】https://www.bilibili.com/video/BV1ET4y1U7T6?p=13&vd_source=4e9b7dd8105df854ae96830c97920252