首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。