说明

面试中常用到的路径规划程序

问题1

从一点到另一点的路径数量。
大致题目
以下图的路径规划为例，每个位置的路径数量为左边和上边的路径数量之和，且边缘的路径均为1，所以路径规划如下
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
切记不可使用排列组合的方法进行计算，因为一旦m和n的值均超过10就会异常

程序

这种题型中最简单的一个，一行就结束了。

/****************************
以下图的路径规划为例，每个位置的路径数量为左边和上边的路径数量之和，且边缘的路径均为1，所以路径规划如下
1
1
1
1
1
1
2
3
4
5
1
3
6
10
15
1
4
10
20
35
切记不可使用排列组合的方法进行计算，因为一旦m和n的值均超过10就会异常
***************************/
int Testlib::uniquePaths(int m, int n)
{
return (m==1||n==1)?1:uniquePaths(m-1,n)+uniquePaths(m,n-1);
}

问题2

路径上各个点都有值，到终点的最小值。
以下图的路径规划为例，每个位置的路径数量为左边和上边的路径数量之和，且边缘的路径均为1，所以路径规划如下
1 2 5 2 4
3 2 3 4 5
2 3 4 10 4
7 4 5 3 9

程序

static int optimalPathHelp(vector<vector<int>>& num, uint m, uint n)
//原函数中最好不要带m,n两个参数，这里是为了方便使用递归，添加m,n用以辅助操作
{
if(m==1&&n==1) return num[0][0];
if(m==1&&n>1) return num[m][n]+optimalPathHelp(num,m,n-1);
if(n==1&&m>1) return num[m][n]+optimalPathHelp(num,m-1,n);
return num[m][n]+optimalPathHelp(num,m-1,n)<optimalPathHelp(num,m,n-1)?optimalPathHelp(num,m-1,n):optimalPathHelp(num,m,n-1);
}
/****************************
以下图的路径规划为例，每个位置的路径数量为左边和上边的路径数量之和，且边缘的路径均为1，所以路径规划如下
1
2
5
2
4
3
2
3
4
5
2
3
4
10
4
7
4
5
3
9
***************************/
int Testlib::optimalPath(vector<vector<int>>& num)
//由于这个num是需要反复进行调用的，改为引用，使得所有的程序均对同一内存操作
{
if(num.empty()) return 0;
uint m=num.size();
uint n=num[0].size();
return optimalPathHelp(num,m,n);
}

最后

实际的面试的题目大概率是在这两种题目上改动得来的，还是需要随机应变的。

最后

以上就是天真红牛为你收集整理的C++路径规划说明问题1问题2最后的全部内容，希望文章能够帮你解决C++路径规划说明问题1问题2最后所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。