分享程序员开发的那些事...
更新时间：2022-08-22 08:27:47
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; }