By yusijia

Updated:

Contents
  1. 1. 定义状态：
  2. 2. 状态转移方程：

//数学三角形问题，有一个由非负整数组成的三角形，第一行只有一个数，除了最下行
之外每个数的左下方和右下方各有一个数

        1
      /   \
    3       2
   /  \   /   \
  4     10      1
 /  \   / \   /  \
4     3     2     20

从第一行的数开始，每次可以往左下或右下走一格，知道走到最下行，把沿途经过的数
全部加起来，如何走才使得这个和尽量大？

定义状态：

d[i][j]为从格子(i,j)出发时能得到的最大和(包括(i,j)本身)。在这个状态
定义下原问题的解是d[1][1]

         1,1
        /   \
      2,1    2,2
     /   \    /  \
   3,1    3,2    3,4
  /  \    /  \  /   \
4,1    4,2     4,3  4,4

第一层1个，第二层2个，第三层3个…..

状态转移方程：

d[i][j] = a[i][j] + max(d[i+1][j], d[i+1][j+1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
//递推计算   //从底往上推
int solve1()
{
    int i, j;
    for(j = 1; j <= n; j++)
        d[n][j] = a[n][j];//先初始化最底层的状态
    for(i = n - 1; i >= 1; i--) //从倒数第二层开始
    {
        for(j = 1; j <= i; j++)
            d[i][j] = a[i][j] + max(d[i+1][j], d[i+1][j+1]);//状态转移方程
    }
}

//递归计算 (从顶往下推)
int solve2(int i, int j)
{
    if(d[i][j] >= 0)//d[i][j]>=0说明该点已经被计算过了
        return d[i][j];
    return d[i][j] = a[i][j] + (i == n ? 0 : max(solve2(i+1, j), solve2(i+1, j+1)));
}//记忆化搜索

int main()
{

    return 0;
}
Contents
  1. 1. 定义状态：
  2. 2. 状态转移方程：