1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/****************************
以下图的路径规划为例，每个位置的路径数量为左边和上边的路径数量之和，且边缘的路径均为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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);
}