題目：數字三角形

創新互聯長期為上千客戶提供的網站建設服務，團隊從業經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態環境。為伽師企業提供專業的做網站、成都網站建設，伽師網站改版等技術服務。擁有十多年豐富建站經驗和眾多成功案例,為您定制開發。

題目介紹：如圖所示的數字三角形，要求從最上方頂點開始一步一步下到最底層，每一步必須下一層，求出所經過的數字的大和。

輸入：第一行值n，代表n行數值；后面的n行數據代表每一行的數字。

輸出：經過數字的大和。

例：

輸入：

4

1

3 2

4 10 1

4 3 2 20

輸出：

24

分析：這也是一個典型的貪心算法無法解決的問題，同樣可以用動態規劃（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;
  }
}

另外有需要云服務器可以了解下創新互聯建站vcdvsql.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網頁名稱：C++數字三角形問題與dp算法-創新互聯
文章路徑：http://vcdvsql.cn/article26/ceoocg.html

成都網站建設公司_創新互聯，為您提供定制開發、營銷型網站建設、網站內鏈、網站設計公司、品牌網站設計、網頁設計公司

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯