tip

数组下标从0开始还是从1开始

如果代码中涉及到数组下标为i-1（有时候哪怕不是同一个数组也符合情况，因为是针对同一组数据进行的多个数组设置），那么我们可以使 i 从 1开始，这样，当 i = 1 时，就取到了[0]，如果这个位置有特殊情况，那么这样一来我们也不必使用 if ，直接对 f [0]设置一个特殊值即可

注意，“输入”与“使用”是统一的，即如果输入数组时决定了使用 i 从 1 开始，那么到时候使用或者取元素时，一定要记得是从 1 开始，
如果输入决定了是从0开始，那么到时候取元素的时候，记得从0开始

数学三角形

介绍

从顶部出发，可以向左下或者右下移动，最后形成一条路径，找到一条路径使得路径上的数字之和最大

算法思想

首先我们对三角形的各个数进行编码，从上到下每行从1开始表上行号，之后，东北方向偏45度进行列号的编排，最左边是1列，之后往右依次是2，3，…，这样一来，我们就可以标定某个元素的位置，这也符合三角形位置的数据在数组内存储时的位置

对于动态规划，仍然是状态表示和状态计算，
状态表示：因为每个元素由一个二维数对进行位置表示，所以，状态表示仍然是一个二维的，如上图所示，属性是max
状态计算：由前面的经验可以总结出：状态计算是一个情况的划分，划分的是上一层的情况，即仅研究上一层即可，之后递推原理会帮助代码完成
上一层的状态有两个，一个来自左上，一个来自右上。
两种划分都是曲线救国的思路，即 f [ i - 1 , j - 1 ] + a[ i , j ]，另一个是 f [ i - 1 , j ] + a[ i , j ]
其中 a数组存储了所有的数据，a [ i , j ]就是表示[ i , j ]位置的值

例题+代码

首先，a[N][N]数组是用来存储所有的数据的
f[N][N]是状态表示

之后，main函数里
首先读入n
之后由于这组数据会涉及到 i-1 ，所以使用数组存数据时，i从1开始到小于等于n，j从1开始到小于等于 i （因为是三角形），读入到a[][]数组中，给[0][x] [x][0]这些位置空出来，方便一些特殊情况时拿来使用（包括a数组自己使用或者其他数组使用，总之这个位置要留出来）
之后初始化状态表示，因为状态表示数组涉及到某一点的上边两个角，所以，要处理好边界问题，我们的 i 从 0开始到等于n，j 从 0开始到等于 i + 1 （这样做可以在原来的数据基础上，多加一个0行和0列被初始化，这样的话，当我们遇到如下图所示情况时，就不会出错了），且f[i][j] = - INF，将所有的位置初始化为负无穷，这样的话，最终原数据的外面的位置下标，f[][]的值是负无穷，这样做是为了当我们有路径来到了原数据的外面，那最后的值一定是负无穷，这样我们就可以筛选出来哪些路径是经过了原数据的外面的位置得到的，这些数据可以排除
之后初始化f[1][1] = a[1][1]，因为第一个还没有经过任何其他的点，可以初始化为1
之后for循环，i 从 2 开始到等于n（之所以从2开始，是因为1就一个节点，已经被初始化了）
二层循环 ，j 从 1 开始到等于i （仍然是因为输入时是三角形输入）
f[ i ][ j ] = max（f[ i - 1 ][j - 1] + a[ i ][ j ] , f[ i - 1 ][ j ] + a[ i ][ j ]）
到此为止，我们就已经可以拿到所有 i j 点的状态了，我们由于是想求最大路径，所以对叶子结点的状态进行求max即可，这里由于之前所有的f都被初始化为了负无穷，所以这样答案也初始化为负无穷去进行比较，而就算有路径经过了负无穷，那最后的值是-INF+一些正数，肯定比-INF要大一点点，所以，res用-INF存储，最后参与到max中

最长上升子序列

介绍

例如这样一个序列，最长子序列就是 1 2 5 6，长度最长是4

算法思想

状态表示可以使用一维的，即所有以“第” i 个数结尾的上升子序列，属性是max
状态计算：
划分依据：上一层是第几个数
如果上一层没有数，那么说明只有“第i个数”这一个数
如果上一层的数是第 j 个数，那么可以递推为 f [ j ] + 1（这个j是有条件的，要满足aj < ai）
最后对所有的f[ j ] + 1 （j从0开始到 i - 1）取max就是答案

例题+代码

a数组表示将数据进行存储，f数组表示状态表示
在mian函数中
首先输入n
i 从 1 到等于n ，输入a[ i ]
之后对for从1到等于n
f[ i ] = 1 ,（所有的 f 最少是1，所以先初始化为1）
之后，对于for循环，j 从 1 开始到小于 i （因为状态计算时，是以" "前一个数"是第几个数 " 进行划分的，所以j从1到小于i，表示遍历所有划分的情况）
同时判断 if （a[j] < a[i]）才是合法的（因为是上升子序列，要求单调）
之后 f[i] = max(f[i] , f[j]+1)（对所有的划分进行max）

最后，把所有的 f[i] 进行取max，即，将所有的情况取最大值，就是最大子序列