首页 > 代码库 > careercup-递归和动态规划 9.2

careercup-递归和动态规划 9.2

9.2 设想有个机器人坐在X*Y网格的左上角,只能向右、向下移动。机器人从(0,0)到(X,Y)有多少种走法?

进阶:

假设有些点为“禁区”,机器人不能踏足。设计一种算法,找到一条路径,让机器人从左上角移动到右下角。

类似leetcode:Unique Paths和Unique Paths II

解法:

我们需要数一数机器人向右X步、向下Y步,总共可以走多少种路径。这条路径总共有X+Y步。

为了走出一条路径,我们实质上要从X+Y步为向右移动。因此,可能路径的总数就是从X+Y项中选出X项的方法总数。具体可以用下面的二项式(又称“n选r”)表示:

 

动态规划实现C++代码:

#include<iostream>#include<vector>using namespace std;//没有障碍时int uniquePaths(int m,int n){    int path[m][n];    int i,j;    for(i=0;i<m;i++)        path[i][0]=1;    for(j=0;j<n;j++)        path[0][j]=1;    for(i=1;i<m;i++)    {        for(j=1;j<n;j++)            path[i][j]=path[i][j-1]+path[i-1][j];    }    return path[m-1][n-1];}//存在障碍时int uniquePathsII(vector<vector<int> > &obstacle){    int m=obstacle.size();    int n=obstacle[0].size();    if(m==0||n==0)        return 0;    int path[m][n];    int i,j;    if(obstacle[0][0]==1)        return 0;    path[0][0]=1;    for(i=1;i<m;i++)    {        if(obstacle[i][0]==1)            path[i][0]=0;        else            path[i][0]=path[i-1][0];    }    for(j=1;j<n;j++)    {        if(obstacle[0][j]==1)            path[0][j]=0;        else            path[0][j]=path[0][j-1];    }    for(i=1;i<m;i++)    {        for(j=1;j<n;j++)        {            if(obstacle[i][j]==1)                path[i][j]=0;            else                path[i][j]=path[i-1][j]+path[i][j-1];        }    }    return path[m-1][n-1];}int main(){    cout<<uniquePaths(3,3)<<endl;    vector<vector<int> > vec={{0,0,0},{0,1,0},{0,0,0}};    cout<<uniquePathsII(vec)<<endl;}

 

careercup-递归和动态规划 9.2