算法-动态规划

0x00 什么是动态规划（dynamic programming）

自己水平有限，解释动态规划比较困难，推荐一个链接，动态规划-漫画

以题目为例子

一个10级的台阶，每次只能一步一步上或者两步两步上，有多少种走法

动态规划有三个点：

1最优化子结构当前状态是又前一步的那几种状态如何选取进而转换来的，我们把n层台阶的走法和记为f(n)，那么：f(10)=f(8)+f(9) 也就是到第10层台阶的走法是到第8层台阶的走法，和到第9层台阶的走法之和（第8层一次走两步就到第十层，第九层一次走一步就到第十层），所以这个问题的最有子结构是：到第8层和第9层分别由多少种走法。

2状态转移方程 f(n)=f(n-1)+f(n-2)即为我们的状态转移方程，且n>2 f(1)=1 f(2)=2 后面的是边界

3无后效性有两层含义，第一层含义是，在推导后面阶段状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

0x01 如何做题

动态规划做题最重要的是如何找到状态转移方程，很多时候并不是一眼就能看出，所以需要我们画图来描述问题，下面以背包问题举例：

01背包问题

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了有M个，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1-5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1,j2,…jk则所求的总和为：

v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。

请你帮助金明设计一个满足要求的购物单。

之所以称为”01背包”，是因为每件物品只有选或者不选两种情况。

这个问题的最优子结构是什么呢？我们把m个物品编号1，2，..m。每个物品的价格为c[i],价值为v[i]，只有n元从m个商品中买的价格重要度乘积和最大，设为f(n,m)，那实际上

①f(n,m)=max(f(n,m-1)，f(n-c[m],m-1)+c[m]*v[m])（n>=c[m]）;

②f(n,m)=f(n,m-1)（n<c[m]）;

③f(n,1)=c[1]*v[1] (n>=c[1]);

④f(n,1)=0 (n<c[1]);

也就是最优子结构是:第m个物品买或者不买两种情况中的最大值。

我在这里直接给出了状态转移方程，是一种自上而下的分析方法，直接分析当前的最优化子结构进而的得到的。如果自上而下分析比较难的时候，我们也可以自下而上的分析，从最简单的问题开始，对于这题，我们可以从1元买1个物品的价格乘积和最大是多少开始，到2元，3元到题目给的n元，然后再从一件物品到两件物品，到三件物品…通过不断的填表从下往上的找规律。

有了状态转移方程，很容易想到用递归实现，递归实现是一个树状的图形，树高为m，所以时间复杂度2^m 是一个指数空间复杂度也是2^m 实际上我们通过观察树的节点，发现很多节点的状态是重复的，我们可以用一个二位数组ans来保存对应的m n时的最大值，这样可以消除重复的节点，时间复杂度为n 空间复杂度m*n。但是空间复杂度还能降低。

注意到我们最终结果都是保存在二维数组ans里，因为有两个变量，但实际上，我们是以m为轴一层一层的往后推进的，实际上只用一个长度为n的一维数组来保存上一层的值和当前这一层的值就行了

int i,k;
int last[n],now[n];
memset(last,0,sizeof(last));
for(i=1;i<=m;i++){
    for(j=0;j<=n;j++){
        if(j>=c[i]){
            now[j]=max(last[j],last[j-c[i]]+c[i]*v[i]);//买的起就买或者不买选最大的情况
        }else{
            now[j]=last[j];//买不起就是上一层一样的情况
        }
    }
    //进行下一层,当前的now变成last了，所以值要放在last里
    for(j=1;j<=m;j++){
    	last[j]=now[j];
    }
}

完全背包问题

完全背包是每个物品可以不限次数的买，那么如果将上面那个题改成完全背包,那么上面的状态转移方程①应该变为：

①f(n,m)=max(f(n,m-1)，f(n-c[m],m)+c[m]*v[m])（n>=c[m]）;

原因在于对于第m个物品，我们有买不起买的起两种情况，上述方程是买得起的情况，但是买得起又分为买一个两个三个….. ，我们不可能一一列举出来,而我们只需要把买了一个第m个物品这种情况算出来之后，继续在这种情况下看再买一个m的情况是多少，一直到买不起m才把m这一层所有情况分析完，所以要把m-1改成还是m。代码如下

int i,j,k;
int last[n],now[n];
for(i=1;i<=m;i++){
    for(j=0;j<=n;j++){
        	now[j]=last[j];//暂且将最大值设置为不买的结果 后面如果比他大就更新
        for(k=1;k*c[i]<=j;k++){
            now[j]=max(now[j],last[j-c[i]*k]+k*c[i]*v[i]);//每次都与前面一个k值的结果now[j]比较
        }
    }
    //进行下一层,当前的now变成last了，所以值要放在last里
    for(j=1;j<=m;j++){
    	last[j]=now[j];
    }
}

int i,k;
int last[n],now[n];
memset(last,0,sizeof(n));//将last清零，这样第一层时结果才正确
for(i=1;i<=m;i++){
    for(j=0;j<=n;j++){
        if(j>=c[i]){
            now[j]=max(last[j],now[j-c[i]]+c[i]*v[i]);  
        }else{
            now[j]=last[j];//买不起就是上一层一样的情况
        }
    }
    //进行下一层,当前的now变成last了，所以值要放在last里
    for(j=1;j<=m;j++){
    	last[j]=now[j];
    }
}

第二种代码用了一个小把戏，是max(last[j],now[j-c[i]]+c[ci].v[i])比较，而now[j-c[i]]是在n更小的情况下的选m个的最大值，如果j-c[i]仍然比从c[i]大，那f[j-c[i]]是能买一个m的情况下的价格重要度乘积和最大的那种情况，我们再加上从c[m].v[m]是再买一个的情况

（有人会问那这里是买两个的m的情况吗？不是的，我刚刚说的f[j-c[i]]是能买一个的情况，但是实际上这个最大值既可能是没买的情况，也可能是买了的情况，所以我们不能说现在再买一个就是买两个m的情况。那有人又问，你这样岂不是能保证你的思路里把买一个买两个一直到买不起的情况都举出来吗？是的，确实不能都列举出来不同个数m时的结果，但是没关系，我们要的时结果的最大情况，如果f[j-c[i]]真的是没买m的结果，那说明不买m的结果比较大，也就是c[m]*v[m]/c[m]的值比较小，化越多钱买第m个这个乘积和越小，所以到底是不是把买不同个数的情况都列出来了，不影响结果。）

多重背包问题

多重背包与完全背包不一样，多重背包是第i个物品最多可以买p[i]个，那么对于第i个物品的可能性我们有如下，买不起（与01背包一样），买一个，买两个，..可以一一列举出来代码和上面的完全背包第一种代码一样

int i,j,k;
int last[n],now[n];
memset(last,0,sizeof(last));
for(i=1;i<=m;i++){
    for(j=0;j<=n;j++){
        	now[j]=last[j];//暂且将最大值设置为不买的结果 后面如果比他大就更新
        for(k=1;k<=p[k];k++){
            now[j]=max(now[j],last[j-c[i]*k]+k*c[i]*v[i]);//每次都与前面一个k值的结果now[j]比较
        }
    }
    //进行下一层,当前的now变成last了，所以值要放在last里
    for(j=1;j<=m;j++){
    	last[j]=now[j];
    }
}

恰好背包问题

恰好背包则是要求把n元恰好全部用完，问价格和重要度的乘积和最大是多少？这个问题我们从上往下分析，装态转移方程如下：

①f(n,m)=max(f(n,m-1)，f(n-c[m],m-1)+c[m]*v[m])（n>=c[m]）;

②f(n,m)=f(n,m-1)（n<c[m]）;

③f(n,0)=0] (n=0);

④f(n,0)=-1000000 (n!=0);

我们从上往下看，从第m个物品一直到第1个物品都考虑完了后，如果剩下的钱为0，那就说明我们该请款下恰好用完，就往该情况上+0，如果不是，那说明前面的选择不能恰好买，所以就加上一个很大的负数，这样在max比较中会被抛弃，保证最后的情况才是恰好的情况，代码如下(01背包的恰好背包)

int i,k;
int last[n],now[n];
for(i=1;i<=n;i++){
    last[i]=-10000;
}
last[0]=0;//把last数组初始化 也就是第0层 除了n=0时一概为-10000；
for(i=1;i<=m;i++){
    for(j=0;j<=n;j++){
        if(j>=c[i]){
            now[j]=max(last[j],last[j-c[i]]+c[i]*v[i]);//买的起就买或者不买选最大的情况（如果）
        }else{
            now[j]=last[j];//买不起就是上一层一样的情况
        }
    }
    //进行下一层,当前的now变成last了，所以值要放在last里
    for(j=1;j<=m;j++){
    	last[j]=now[j];
    }
}

分组背包

分组背包是有m组物品，每组有p[m]个,价格为c[m] [p[m]],重要度为v[m] [p[m]],只能从每个组里选一个，求价格重要度乘积最大值。这其实和多重背包有点类似，我们在选每一组时，有p[m]种情况，所以还是和多重背包一样，在这p[m]种情况里找最大的

int i,j,k;
int last[n],now[n];
memset(last,0,sizeof(last));
for(i=1;i<=m;i++){
    for(j=0;j<=n;j++){
        now[j]=last[j]//先暂且确定为不买 最大
        for(k=1;k<=p[i];k++){
            now[j]=max(now[j],last[j-c[i][p[i]]]+c[i][p[i]]*v[i][p[i]])
        }
    }
    //进行下一层,当前的now变成last了，所以值要放在last里
    for(j=1;j<=m;j++){
    	last[j]=now[j];
    }
}

有依赖的背包

未完待续…