careercup-递归和动态规划 9.2

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

进阶：

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

解法：

我们需要数一数机器人向右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=;i<m;i++)

        path[i][]=;

    for(j=;j<n;j++)

        path[][j]=;

    for(i=;i<m;i++)

    {

        for(j=;j<n;j++)

            path[i][j]=path[i][j-]+path[i-][j];

    }

    return path[m-][n-];

}

//存在障碍时

int uniquePathsII(vector<vector<int> > &obstacle)

{

    int m=obstacle.size();

    int n=obstacle[].size();

    if(m==||n==)

        return ;

    int path[m][n];

    int i,j;

    if(obstacle[][]==)

        return ;

    path[][]=;

    for(i=;i<m;i++)

    {

        if(obstacle[i][]==)

            path[i][]=;

        else

            path[i][]=path[i-][];

    }

    for(j=;j<n;j++)

    {

        if(obstacle[][j]==)

            path[][j]=;

        else

            path[][j]=path[][j-];

    }

    for(i=;i<m;i++)

    {

        for(j=;j<n;j++)

        {

            if(obstacle[i][j]==)

                path[i][j]=;

            else

                path[i][j]=path[i-][j]+path[i][j-];

        }

    }

    return path[m-][n-];

}

int main()

{

    cout<<uniquePaths(,)<<endl;

    vector<vector<int> > vec={{,,},{,,},{,,}};

    cout<<uniquePathsII(vec)<<endl;

}

巴特西

careercup-递归和动态规划 9.2

最新文章

热门文章