C++数字三角形问题与dp算法-创新互联

题目:数字三角形

创新互联长期为上千客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为伽师企业提供专业的做网站、成都网站建设,伽师网站改版等技术服务。拥有十多年丰富建站经验和众多成功案例,为您定制开发。

题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的大和。

输入:第一行值n,代表n行数值;后面的n行数据代表每一行的数字。

输出:经过数字的大和。

例:

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

输入:

4

1

3 2

4 10 1

4 3 2 20

输出:

24

分析:这也是一个典型的贪心算法无法解决的问题,同样可以用动态规划(dp算法)来解决。把边界数字首先初始化到结果矩阵中,再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形,与传统的状态方程相比需要做点改进。

数组编号:

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

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

代码如下:

#include 
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;
  }
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


新闻标题:C++数字三角形问题与dp算法-创新互联
文章来源:http://scyanting.com/article/ceoocg.html