数字三角形「动态规划」

数字三角问题

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

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

分析

• 采用暴搜每次把每个点能经过的路线全部找出，但是对于层 数字三角形的完整路线有条，当很大时，是定不行的。 会超时，那有什么好方法呢？
• 把当前的位置看成一个状态，表示的是从格子出发能取到的最大和(包括本身的值),原问题的解就是。
• 不同的状态怎么转移呢？从格子出发有两种决策。左走下个格子是，右走下个格子是，但是对于(i,j)来说，它只取两者中大的那个。于是状态转移方程就是：
  
  每个格子都有这样的选择，于是每个格子存放的都是从格子能取到的最大值。
• 如果从格子中向下取数其中一个格子存放的不是最大值，那么就一定不是最大的。这个性质称为最优子结构。(全局最优解包含局部最优解)

「动态规划的核心是状态和状态转移方程」

方法1：递归计算()各点的

int solve(int i,int j)
{
   return a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));
}

重叠子问题
如图调用的关系树，发现红色的部分计算调用了两次。虽然图中只有这几个点被重复，但是重复的不仅仅是单个节点，而是节点下的整棵子树。加入三角形有n层，那么调用关系树就有n层，一共有个节点。

「直接采用递归的方法计算状态转移方程，效率往往十分低下。原因就是相同的子问题被重复计算了很多次」

为了解决直接采用递归会超时，我们提出记忆化搜索，通常采用一个记忆数组，记录每个状态是否已经计算过。于是要初始化记忆数组

方法2 记忆化搜索+递归

int solve(int i,int j)
{
   if(dp[i][j]>=0)//记忆数组（i,j)已经算出直接返回
   {
       return dp[i][j];
   }
   return dp[i][j]=a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));
}

有了这个记忆化数组，就可以保证每个节点只访问一次。

记忆化搜索
「当采用记忆化搜索时，不必事先确定各状态的计算顺序，但需要记录每个状态“是否已经计算过”」

方法3 直接递推

for(int i=1;i<=n;i++)
{
    dp[n][i]=a[n][i];
}
for(int i=n-1;i>=1;i--)
{
     for(int j=1;j<=i;j++)
     {
          dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
     }
}