动态规划 -- 杨辉三角

f756eade65a5da08e7c0f1e93f9f20cc.jpg

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

#include<iostream>
using namespace std;

int matrix[5][5] = { { 5 },{ 7,8 },{ 2,3,4 },{ 4,9,6,1 },{ 2,7,9,4,5 } };

int main()
{
    int status[5][8];
    status[0][0] = 5;
    for (int i = 1;i < 5;i++)
    {
        for (int j = 0;j <=i;j++)
        {
            if(j==0)
                status[i][j] = status[i - 1][j] + matrix[i][j];
            else if (j > 0 && j < i)
            {
                int v = status[i - 1][j] + matrix[i][j];
                int w = status[i - 1][j - 1] + matrix[i][j];
                if (v < w)
                    status[i][j] = v;
                else
                    status[i][j] = w;
            }
            else if (j == i)
                status[i][j] = status[i - 1][j - 1] + matrix[i][j];
        }
    }
    int min = status[4][0];
    for (int w = 1;w < 5;w++)
    {
        if (status[4][w] < min)
            min = status[4][w];
    }
    cout << min << endl;
    system("pause");
}