极客时间：第40章课后习题之杨辉三角

 1 #include <iostream>
 2 #include <math.h>
 3 #include <string>
 4 #include <vector>
 5 #include <map>
 6 #include<memory.h>
 7 using namespace std;
 8 
 9 //先求出最短路径长度，再算出是哪些路径
10 const int MaxLen = 15;
11 const int MaxCeng = 5;
12 int Pos2Value[MaxLen] = {5,7,8,2,3,4,4,9,6,1,2,7,9,4,5};
13 int Pos2Shot[MaxLen] = {5,7,8,2,3,4,4,9,6,1,2,7,9,4,5};
14 int Ceng2Pos[MaxCeng + 1] = {0,1,3,6,10,16};
15 
16 int FindShot()
17 {
18     //计算每个pos最短从上往下遍历
19     for (int nCurCeng = 1; nCurCeng < MaxCeng; ++nCurCeng)
20     {
21         int nLastCengFirst = Ceng2Pos[nCurCeng - 1];
22         Pos2Shot[Ceng2Pos[nCurCeng]] += Pos2Shot[nLastCengFirst];    //边缘化数据只有每行第一个和最后一个，为了提高循环效率，单独拿出来处理
23         Pos2Shot[Ceng2Pos[nCurCeng+1] - 1] += Pos2Shot[Ceng2Pos[nCurCeng] - 1];
24         for (int nLine = Ceng2Pos[nCurCeng] + 1; nLine < Ceng2Pos[nCurCeng+1] - 1; ++nLine)
25         {
26             Pos2Shot[nLine] += min(Pos2Shot[nLastCengFirst] - 1, Pos2Shot[nLastCengFirst]);
27             ++nLastCengFirst;
28         }
29     }
30     //求最后一层最短
31     int nResMin = 100000;
32     for (int i = Ceng2Pos[MaxCeng-1]; i<Ceng2Pos[MaxCeng]-1; ++i)
33     {
34         if (nResMin > Pos2Shot[i])
35         {
36             nResMin = Pos2Shot[i];
37         }
38     }
39     cout<< nResMin<<endl;
40     //如果结果正确，倒推出满足最短路径的哪些pos
41 
42     return nResMin;
43 }
44 int main()
45 {
46     FindShot();
47     return 0;
48 }