C++数字三角形问题与dp算法

数组编号：

状态方程：p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]}

代码如下：

#include <iostream>
using namespace std;
int main()
{
  int i;
  int n;
  cin >> n;
  int **p = new int *[n];
  for (i = 0; i < n; i++)
  {
    p[i] = new int[n];
  }
  for (i = 0; i < n; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      cin >> p[i][j];
    }
  }
  for (i = 1; i < n; i++)
  {
    p[i][0] += p[i - 1][0];
  }
  for (i = 1; i < n; i++)
  {
    p[i][i] += p[i - 1][i - 1];
  }
  for (i = 2; i < n; i++)
  {
    for (int j = 1; j < i; j++)
    {
      p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j];
    }
  }
  for (i = 0; i < n; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      cout << p[i][j] << " ";
    }
    cout << endl;
  }
}