动态规划是一种思想，大规模的问题的依赖于小规模问题的计算结果。他主要解决三大类问题：求最值，求方案可行性，求方案总数。

动态规划专题 - 图1

自顶向上的动态规划

题目描述：每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
image.png

  1. class Solution {
  2. public:
  3.     int minimumTotal(vector<vector<int>>& triangle) {
  4.         vector<vector<int>> array = triangle;
  5.         int len = array.size();
  6.         for(int i = 0; i < len - 1; i++)
  7.         {
  8.             for(int j = 0; j < i + 1; j++)
  9.             {
  10.                 array[i][j] = 0;
  11.             }
  12.         }
  14.         for(int i = len - 2; i > -1; i--)
  15.         {
  16.             for(int j = 0; j < i + 1; j++)
  17.             {
  18.                 array[i][j] = min(array[i + 1][j], array[i + 1][j + 1]) + triangle[i][j];         
  19.             }
  20.         }
  21.         return array[0][0];
  22.     }
  23. };

思路：先求出倒数第二层到最底层的最短路径，然后逐步向上求解。

动态规划四要素

动态规划的状态
用数组代表在某些特定条件下某个规模更小的问题和答案
规模更小用参数i,j之类的来划定
动态规划的方程
大问题如何拆解为小问题
f[i][j]=通过规模更小的一些状态来进行推到
动态规划的初始化
设定无法再拆解的极限笑的状态下的值
如f[i][0]或者f[0][i]
动态规划的答案
最后要求的答案是什么