本文共 1764 字，大约阅读时间需要 5 分钟。

动态规划题目：

“杨辉三角”不知道你听说过吗？我们现在对它进行一些改造。每个位置的数字可以随意填写，经过某个数字只能到达下面一层相邻的两个数字。

设你站在第一层，往下移动，我们把移动到最底层所经过的所有数字之和，定义为路径的长度。请你编程求出从最高层移动到最底层的最短路径长度。

分析：

• 将题目中的“杨辉三角”放入矩阵中
  
• 重新改写题目：从(1,A)开始的node，只能向右、向下移动，求到达边界时【边界：即过(5,A) 、(1,E）的直线】的最短路径【最短路径：路线上经过各点数的和最小】。
• 矩阵初始化，给边界求和
  
• 内部求值策略：当前值为选取两个方向：左侧、上方值的最小值，加上当前的路径值。[i,j] = [i,j] + min([i-1,j],[i,j-1])
  
• 依次类推
  
• 结论：最短路径为20
• 代码实现

// Example program#include 
   
    #include 
    
     using namespace std;void print_m(int n, int (*matrix)[5]){
       for (int i = 0; i < n; ++i)    {
           for (int j = 0; j < n; ++j)        {
               cout << matrix[i][j] << " ";        }        cout << endl;    }    cout << "~~~~~~~~~~~" << endl;}int main(){
       int matrix[][5] = {
   {
   5, -1, -1, -1, -1}, {
   7, 8, -1, -1, -1}, {
   2, 3, 4, -1, -1}, {
   4, 9, 6, 1, -1}, {
   2, 7, 9, 4, 5}};    print_m(5, matrix);    // 整理数据    for (size_t col = 0; col < 5; col++)    {
           while (matrix[0][col] == -1)        {
               for (size_t row = 1; row < 5; row++)            {
                   swap(matrix[row - 1][col], matrix[row][col]);            }        }    }        print_m(5, matrix);    // 动态规划算法    // step1 ：初始化0行    for (size_t i = 1; i < 5; i++)    {
           matrix[0][i] +=  matrix[0][i-1];    }    print_m(5, matrix);    // step2 ：初始化0列    for (size_t j = 1; j < 5; j++)    {
           matrix[j][0] +=  matrix[j-1][0];    }    print_m(5, matrix);    // step3: 计算内部的值    for (size_t i = 1; i < 5; i++)    {
           for (size_t j = 1; j < 5; j++)        {
              matrix[i][j] += min
     
      (matrix[i-1][j],matrix[i][j-1]);        }    }    print_m(5, matrix);    // step4：取边界上的最小值    int idx = 4;    vector
      
        v;    do    {
         v.push_back(matrix[idx][4-idx]);    } while (0
      
     
    
   

转载地址：http://eecii.baihongyu.com/