输入格式：

5 // 三角形行数，下面是三角形

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

三角形的行数大于1小于等于100，数字为 0 – 99。

要求输出最大和，不必给出具体路径。

---

思路

• D(r,j)：第r行第j个数字（r，j从1开始算）
• MaxSum(r,j)：从D(r,j)到底边的各条路径中，最佳路径的数字之和

问题：求MaxSum(1,1)

D(r,j)出发，下一步只能走D(r+1,j)或者D(r+1,j+1)

对于N行的三角形：

if(r == N)    MaxSum(r,j) = D(r,j)else    MaxSum(r,j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)

---

递归

#include
     
      #include
      
       #define MAX 101using namespace std;int D[MAX][MAX];int n;int MaxSum(int i, int j) {    if(i == n)        return D[i][j];    int x = MaxSum(i+1,j);    int y = MaxSum(i+1,j+1);    return max(x,y) + D[i][j];}int main(){    cin>>n;    for(int i=1; i<=n; i++)        for(int j=1; j<=i; j++)            cin>>D[i][j];    cout<< MaxSum(1,1) <
      
     

---

改进

每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。

---

记忆递归型动态规划

#include
     
      #include
      
       #define MAX 101using namespace std;int D[MAX][MAX];int n;int maxSum[MAX][MAX];int MaxSum(int i, int j) {    if(maxSum[i][j] != -1)        return maxSum[i][j];    if(i == n)        maxSum[i][j] = D[i][j];    else {        int x = MaxSum(i+1,j);        int y = MaxSum(i+1,j+1);        maxSum[i][j] = max(x,y) + D[i][j];    }    return maxSum[i][j];}int main() {    cin>>n;    for(int i=1; i<=n; i++)        for(int j=1; j<=i; j++) {            cin>>D[i][j];            maxSum[i][j] = -1;        }    cout<< MaxSum(1,1) <
      
     

---

30
23	21
20	13	10
7	12	10	10
4	5	2	6	5

递推型动态规划

#include
     
      #include
      
       #define MAX 101using namespace std;int D[MAX][MAX];int n;int maxSum[MAX][MAX];int main() {    cin>>n;    for(int i=1; i<=n; i++)        for(int j=1; j<=i; j++)            cin>>D[i][j];    for(int i=1; i<=n; i++)        maxSum[n][i] = D[n][i];    for(int i=n-1; i>=1; i--)        for(int j=1; j<=i; j++)            maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];    cout<
       
        <
       
      
     

---

空间优化动态规划

用D的第n行替代maxSum

#include
     
      #include
      
       #define MAX 101using namespace std;int D[MAX][MAX];int n;int *maxSum;int main() {    cin>>n;    for(int i=1; i<=n; i++)        for(int j=1; j<=i; j++)            cin>>D[i][j];    maxSum = D[n];  // maxSum指向第n行    for(int i=n-1; i>=1; i--)        for(int j=1; j<=i; j++)            maxSum[j] = max(maxSum[j], maxSum[j+1]) + D[i][j];    cout<
       
        <
       
      
     

---

北大的公开课真心不错，感觉比现在上的算法课好很多(●’◡’●)