数字三角形是一个非常有趣的数学问题，它可以用来训练程序员的逻辑思维和编程能力。本文将介绍使用 C++ 实现数字三角形的代码。

数字三角形问题是这样的：给定一个数字三角形，每个位置有一个数字，从顶部出发，每次可以走到下一行的相邻位置，求出从顶部到底部的路径中数字和最大的路径，并输出该路径上的数字。

下面是一个数字三角形的示例：

  7
 3 8
8 1 0
2 7 4 4

使用 C++ 实现数字三角形的解法主要有两种，分别是递归和动态规划。这里介绍使用动态规划实现数字三角形的代码。

先定义一个二维数组 `triangle`，其中第 `i` 行第 `j` 列的元素表示数字三角形中第 `i` 行第 `j` 列的数字。再定义一个二维数组 `dp`，其中第 `i` 行第 `j` 列的元素表示从数字三角形的顶部到第 `i` 行第 `j` 列的数字的最大路径和。接下来，使用以下代码实现动态规划的递推过程：

for (int i = 0; i < n; i++) {
  for (int j = 0; j <= i; j++) {
    if (i == 0) {
      dp[i][j] = triangle[i][j];
    } else if (j == 0) {
      dp[i][j] = dp[i-1][j] + triangle[i][j];
    } else if (j == i) {
      dp[i][j] = dp[i-1][j-1] + triangle[i][j];
    } else {
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
    }
  }
}

最后，我们需要找到从顶部到底部的路径中数字和最大的路径，并输出该路径上的数字。使用以下代码实现：

int maxSum = -1;
for (int i = 0; i < n; i++) {
  if (dp[n-1][i] > maxSum) {
    maxSum = dp[n-1][i];
    maxIndex = i;
  }
}
cout << "The maximum sum of the path is " << maxSum << endl;
vector<int> path;
path.push_back(triangle[n-1][maxIndex]);
int i = n-2, j = maxIndex;
while (i >= 0) {
  if (j == 0) {
    path.push_back(triangle[i][j]);
    j++;
  } else if (j == i+1) {
    path.push_back(triangle[i][j-1]);
    j--;
  } else {
    if (dp[i][j-1] > dp[i][j]) {
      path.push_back(triangle[i][j-1]);
      j--;
    } else {
      path.push_back(triangle[i][j]);
      j++;
    }
  }
  i--;
}
reverse(path.begin(), path.end());
cout << "The path is ";
for (int k = 0; k < path.size(); k++) {
  cout << path[k] << " ";
}

完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      cin >> triangle[i][j];
    }
  }
  // dynamic programming
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      if (i == 0) {
        dp[i][j] = triangle[i][j];
      } else if (j == 0) {
        dp[i][j] = dp[i-1][j] + triangle[i][j];
      } else if (j == i) {
        dp[i][j] = dp[i-1][j-1] + triangle[i][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
      }
    }
  }
  // find max sum path and output the path
  int maxSum = -1;
  int maxIndex = -1;
  for (int i = 0; i < n; i++) {
    if (dp[n-1][i] > maxSum) {
      maxSum = dp[n-1][i];
      maxIndex = i;
    }
  }
  cout << "The maximum sum of the path is " << maxSum << endl;
  vector<int> path;
  path.push_back(triangle[n-1][maxIndex]);
  int i = n-2, j = maxIndex;
  while (i >= 0) {
    if (j == 0) {
      path.push_back(triangle[i][j]);
      j++;
    } else if (j == i+1) {
      path.push_back(triangle[i][j-1]);
      j--;
    } else {
      if (dp[i][j-1] > dp[i][j]) {
        path.push_back(triangle[i][j-1]);
        j--;
      } else {
        path.push_back(triangle[i][j]);
        j++;
      }
    }
    i--;
  }
  reverse(path.begin(), path.end());
  cout << "The path is ";
  for (int k = 0; k < path.size(); k++) {
    cout << path[k] << " ";
  }
  cout << endl;
  return 0;
}

以上就是使用 C++ 实现数字三角形代码的具体步骤，希望能对大家的学习和开发有所帮助。

相似文章
• C++生成随机数的代码
  C++是一种非常常用的编程语言，它可以实现各种各样的功能，如生成随机数。下面将介绍如何在C++中生成随机数的代码。
  
  
• C++代码：学生信息管理系统
  学生信息管理系统是一款基于C++语言开发的应用程序，它主要用于管理学生的个人信息，包括学生的姓名、性别、年龄、学号、专业等相关信息。该系统能够帮助学校方便地查询和管理学生信息，方便学生及其家长了解学生个人发展状况，也方便教师了解学生在学习生
  
  
• 如何运行VC++代码
  VC++是一种广泛使用的编程语言，旨在开发Windows应用程序。如果您是想使用VC++编写程序或者想了解如何运行VC++代码的初学者，本文将为您介绍如何安装VC++开发环境以及运行VC++代码的步骤。
  
  
• 如何将c++登录界面与代码相连接
  在软件开发过程中，登录界面是非常常见的一个功能，而C++也是一种常用的编程语言。在本文中，我们将介绍如何将C++登录界面与代码相连接，实现简单的用户登录功能。
  
  
• C++代码：将二维数组(5行5列)的周围放0
  在编程过程中，有时候需要将一些数据进行处理，以满足我们的需求。其中，二维数组是一种常用的数据结构，在很多场景中都能够使用。今天，我来跟大家分享一下如何将二维数组(5行5列)的周围放0。
  
  
• C++无限循环：如何避免代码陷入死循环？
  C++是一种广泛应用于编程的高级语言，它有着强大的数据处理能力和方便的代码编写性。然而，由于语言的特点，开发过程中经常会出现一些问题。其中最要命的问题之一就是循环陷阱。
  
  
• C++Word插入页码的代码
  C++Word是一种强大的编程语言，提供许多有用的功能，例如插入页码。以下是C++Word插入页码的代码：
  
  
• C++求三个数中的最大值代码
  在编程语言中，找到一组数字中的最大值是非常常见的操作。这种操作可以帮助我们解决许多实际问题，如寻找最高分、最大货物数量等。在C++中，寻找三个数中的最大值也非常简单，只需要使用if语句和条件比较操作即可。
  
  
• 如何运行VC++6.0代码？
  VC++6.0
  
  
• C++矩阵乘法代码实现
  矩阵乘法是一种基本的线性代数运算，对于数据处理和计算机图形学等领域都有着广泛的应用。在C++中，实现矩阵乘法可以利用数组和循环语句实现。
  
  
• Scratch转换为C++代码
  Scratch是一款易于学习和使用的编程语言，主要面向儿童和初学者。然而，当对编程语言的掌握程度渐渐深入时，我们希望使用更高效的语言来编写程序并优化运行效率。因此，将Scratch代码转换为C++代码是一种很好的选择。
  
  
• 如何编写简单的Java小游戏代码？
  Java是一种广泛使用的编程语言，它可以用来编写各种类型的应用程序，包括游戏。编写JAVA小游戏代码并不难，只需要按照以下步骤，你就可以轻松搞定。
  
  
• C++实现二维数组转置：方法及代码
  在C++中，二维数组转置是一个常见的操作。它可以将矩阵进行行列互换，使得原本的行变成列，列变成行。这在一些矩阵运算和图像处理中都有很多的应用。本文将介绍如何使用C++实现二维数组的转置，并提供相应的代码。
  
  
• C++ DLL代码无法调试的解决方案
  C++
  
  
• "扫描C++游戏代码，创建精彩游戏体验"
  近年来，随着游戏行业的不断发展，越来越多的游戏开发者开始使用C++语言编写游戏代码。C++语言以其高效性、灵活性和可移植性，成为游戏开发者的首选编程语言。
  
  
• 完整的C++程序例程
  C++是一种功能强大的编程语言，它可以用于多种应用程序和系统。下面是一份完整的C++程序例程，让我们来看看它是如何工作的。
  
  
• "使用C++编写二叉树数据结构的代码"
  二叉树是一种常用的数据结构，它可以用于模拟树形关系，支持快速查找、插入和删除操作。在计算机科学领域中，使用C++编写二叉树数据结构的代码是非常常见的。
  
  
• C++二分查找算法代码
  二分查找算法是一种高效的搜索算法，通常用于在有序数组中查找某个元素。C++作为一种流行的编程语言，也提供了二分查找算法的代码实现。下面是一个简单的C++二分查找算法的代码示例：
  
  
• C++编程: 求平均数的代码
  C++编程是一门让人着迷的技术。它具有非常丰富的功能和语法，使得它成为了许多程序员们最喜欢使用的编程语言之一。这里，我们将给大家分享一个基本的C++编程知识：如何使用C++编写一个求平均数的代码。
  
  
• C++编写求公因数的代码
  C++是一种经典的编程语言，被广泛应用于软件开发、游戏开发、嵌入式开发等领域。在编写C++代码时，我们经常需要解决一些数学问题，其中求公因数是常见需求之一。本文将介绍如何用C++编写求公因数的代码。
  
  
• C++整数相加代码实例
  C++语言是一种高级编程语言，其包含了许多自带函数，这些函数可以帮助你完成各种任务，包括数学计算。在本篇文章中，我们会介绍如何使用C++语言编写一个整数相加的代码实例。
  
  
• C++编写画直线的代码
  C++是一种通用编程语言，广泛应用于计算机科学领域的各个方面。其中，画图是C++应用最广泛的领域之一。对于初学者来说，学会如何画直线是入门的第一步。下面将介绍C++编写画直线的代码。
  
  
• 编写Java软件
  随着时代的发展，软件行业也发生了翻天覆地的变化，Java作为一门优秀的编程语言被广泛应用于软件开发领域。Java软件可以运行在多个平台上，具有高效、可靠、安全等特点。因此，学习和掌握Java编程技术已成为程序员们的必修课。
  
  
• 「超级娱乐」：令人欢乐的C++编程代码
  C++编程语言是一门强大的语言，它不仅可以用于计算机的科学运算，还可以用来开发游戏和娱乐应用。在这篇文章中，我们将介绍一些有趣的C++编程代码，这些代码可以帮助你创建各种娱乐应用，例如游戏和音乐播放器。
  
  
• 如何在C++中编译和运行代码
  C++是一种高效，快速和通用的编程语言，它是在C语言基础上发展而来。在学习C++编程时，编译和运行你的代码是最基本的步骤。在这篇文章中，我们将探讨如何在C++中编译和运行代码。
  
  
• VC++6.0 编写小鱼游动代码
  VC++6.0是微软公司推出的一款C++编程语言开发环境。其强大的功能和广泛的应用使得VC++6.0成为众多软件开发人员的首选。在VC++6.0中，我们可以编写出各种各样的程序，其中包括小鱼游动代码。
  
  
• C++ 连接数据库的代码
  C++是一门面向对象的编程语言，在实际开发中经常需要将程序与数据库进行连接。本文将介绍C++连接数据库的代码。
  
  
• C++代码实现简单烟花特效
  烟花特效是游戏和动画中常用的一个特效，它给人一种华丽、炫酷的感觉。本文将介绍一种使用C++实现简单烟花特效的方法。
  
  
• C++注释代码的方法及技巧
  C++是一种非常常用的编程语言，其代码通常需要一定程度的注释才能更加易读易懂。本文将介绍C++注释代码的方法及技巧。
  
  
• 如何使用C++编写年月日输出代码
  随着计算机技术的发展，编程语言也越来越多，其中C++语言因为其强大的功能和广泛的应用领域而备受程序员的青睐。如果你想要使用C++语言编写一个可以输出年月日的代码，下面就为你提供详细的实现步骤。
  
  
• 使用C++绘制圆形
  C++是一种广泛使用的编程语言，其功能十分强大，包括绘图功能。如果你想绘制一个圆形，那么C++就是一个绝佳的选择。
  
  
• C++代码：求三个数的平均数
  C++语言是一种高级编程语言，广泛用于软件开发和算法设计。在C++中，求三个数的平均数是一种常见的算法问题，它涉及到基本的数学和编程知识。本文将介绍如何用C++语言实现求三个数的平均数的算法。
  
  
• C++死循环代码实例
  C++是一种高级编程语言，它在很多领域都有着广泛的应用。在编写C++代码时，我们有时会因为一些小错误而造成程序陷入死循环，这会给我们带来很多麻烦。本文将介绍一些C++死循环代码实例，以帮助大家更好地理解和避免死循环的发生。
  
  
• C++代码制作生日蛋糕
  在程序员的世界里，没有什么事是不能通过编程实现的。那么，你是否曾想过用C++代码制作一份生日蛋糕呢？下面，我将为你介绍一下如何用C++代码制作生日蛋糕。
  
  
• 如何在C++中注释掉一段代码？
  在C++中，注释是一种特殊的标记，它用于在代码中添加注释或排除代码段，以帮助其他人更好地理解你的代码。在本文中，我们将介绍如何注释掉一段C++代码。
  
  
• C++栈代码
  C++是一种高效的编程语言，用于开发各种应用程序和软件项目。其中，栈是一种非常基本和重要的数据结构，常用于数据存储和处理过程中。
  
  
• 如何在C++2010中打完代码后停留在结果界面
  在C++2010中，打完代码后，程序往往会在一瞬间完成运行并自动关闭。如果想要在程序运行结束后停留在结果界面，可以使用以下方法：
  
  
• C++猜拳游戏代码
  猜拳是一种充满乐趣的休闲游戏，现在我们可以使用C++语言来实现这个游戏。下面是一份简单的C++猜拳游戏代码。
  
  
• "C++程序输出示例"
  C++是一种常用的编程语言，在计算机科学的学习和开发中扮演着很重要的角色。在C++中，程序的输出是我们非常重要的一个方面，因为它可以通过在屏幕上打印出来的信息以及将数据保存到文件中的方式向用户提供反馈和结果。
  
  
• C++计算字符串长度的代码
  C++是一种广泛使用的编程语言，它被广泛应用于计算机科学和其他各种行业。其中计算字符串长度是C++中常用的一个操作，下面我们将介绍如何使用C++编写计算字符串长度的代码。
  
  
• 为什么在C++中打出菱形代码时，中文会变成乱码？
  在使用C++编写代码时，很多人可能会遇到一个奇怪的问题，就是当使用中文字符打出菱形代码时，中文文字会变成乱码。这是一个很常见的问题，但是其原因却不太简单。
  
  
• C++语言代码大全：汇总所有常用C++代码
  C++语言是一种优秀的编程语言，它具有高效、灵活、稳定等优点，被广泛应用于软件开发、嵌入式系统、游戏制作等领域。
  
  
• 如何编写C++斐波那契数列代码
  斐波那契数列是一组非常有趣的数字序列，该序列每个数字都是前两个数字的和。这个序列以0和1开始，之后的数字就是前两个数字的和，如下所示：0、1、1、2、3、5、8、13、21……
  
  
• Visual Studio Code中如何运行C++代码
  在Visual
  
  
• C++指针加密：保护代码不被破解
  在当今互联网时代，随着计算机技术的不断发展，许多黑客和骇客都会利用各种手段试图入侵系统，窃取和篡改数据，尤其是针对软件程序进行破解，这已经成为一种普遍的现象。
  
  
• Dev C++运行框背景颜色代码
  Dev
  
  
• 如何在C++2010中仅运行代码而不编译？
  如果你想在C++2010中仅运行代码而不编译，有以下几种方法可选：
  
  
• C++部分正确
  C++语言是一门十分重要的编程语言，它是一种面向对象的语言，并且具有高效、灵活、可移植的特点，广泛应用于软件开发、游戏开发、嵌入式系统等领域。但是，就像其他编程语言一样，C++也存在着一些问题。
  
  
• C++语言编写求圆周率的代码
  C++是一种高级编程语言，被广泛应用于计算机科学和软件开发领域。其中，求圆周率的算法便是C++编程中的一个常见问题。下面将介绍如何用C++语言编写一个简单的求圆周率的程序。
  
  
• Java 调用执行 Python 代码
  Java和Python是两种不同编程语言，它们有不同的运行方式和特点。但是，有些时候我们需要在Java中调用执行Python代码，这时候该怎么做呢？
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政