数据结构 （数组和矩阵,初级动态规划）

下面的图来自数据结构朱允刚老师

多维数组：

        eg:已知A[3][5][11][3],请问 A[i][j][k][l]的地址是多少   假设A的数据类型是 T

                A + (i*165+j+33+3*k+l)* sizeof T（默认按行优先存储，如果是按列优先存储就反过来）

                A + ( i + 3j + 15k + 165l ) * sizeof T

矩阵的压缩技术

        对角矩阵：d[i]储存m[i][i]

       （以下都假设是n*n矩阵,默认行优先，如果列优先就反着来）

        上三角矩阵：（i<=j）的数据有效

        下三角矩阵：（i>=j）的数据有效

               下三角的压缩： m[i][j]是d数组的第几个 ：d[ i * ( i - 1 ) / 2 + j-1 ]

                元素个数：（n+1）*n/2

        对称矩阵（m[i][j]==m[j][i]）结论如下：

        题目：

        三对角矩阵压缩

        稀疏矩阵的压缩：

                1，三元组表（i,j,val）可以用tuple来表示，也可以自己定义一个结构体

                2，十字链表法

                有n+m个哨兵节点用于标记我们的行与列（感叹老师的图画的太好了）

        初始动态规划：

                我的理解是如果一个任务，可以被划分为多个相同前提条件的规模更小的子任务的时候，就可以利用动态规划来解决

        就像是普通的背包问题，前提条件都是现在的体积和i个物品，，当我们要知道前i个物品的情况的时候，本质就是前提条件都是已知体积和i-1个物品的情况现在考虑第 i 个物品

        可以发现当我们已知一个规模更小的子任务时，就可以思考出一个规模更大的任务了

        eg:小青蛙跳楼，可以跳1、2个台阶一次,有多少个跳法(0开始）

        f[1]=1 ;f[2]=2;

        f[i]=f[i-1]+f[i-2];

LL C(int n,m){       

         LL ans =1;

        for(int i=n-m+1,j=1;i<=n;i++,j++)ans=ans*i/j;

        return ans;

}

        最大子数组和：
int maxsubarr(int a[],int n){

        int f=a[0];

        int res=f;

        for(int i=1;i<n;i++){

                f=max(a[i],f+a[i]);

                res=max(f,res);

        }

        return res;

}