线性动态规划

例子: 一个含有n阶的楼梯，一次可以走1步或2步，从底走到顶一共有几种走法？

#include <stdio.h>
int fun(int);


int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n", fun(n));
    return 0;
}

int fun(int m)
{
    if (m == 1) 
        return 1;
    else if (m == 2)
        return 2;
    else 
        return fun(m - 1) + fun(m - 2);
}

但是显然，如下图：

会出现大量重复计算，因此我们将已经计算过的项用一个数组保存下来，在需要时直接调用：

#include <stdio.h>

int f[100];//保留已计算的值
int b[100];//标记是否已经计算


int fun(int n)
{
    if (b[n] == 0)//这个数还没有被计算过
    {
        f[n] = fun(n - 1) + fun(n - 2);
        b[n] = 1;//现在算好了呀
    }
    return f[n];
}

int main()
{
    f[1] = 1;
    f[2] = 1;//0扔掉，0看着烦人
    int n,i;
    scanf("%d", &n);
    for (i = 3; i < n; i++)
        b[n] = 0;//尚未计算
    b[1] = 1;
    b[2] = 1;//已知
    printf("%d\n", fun(n));
    return 0;
}

完美✌

用动态规划解决背包问题

先讲一下二维dp：
让我假设现在的背包的容量是C=10；
物品编号： 1 2 3
物品重量： 5 6 4
物品价值：20 10 12
用v[i]表示物品价值，w[i]表示物品重量，要使得放入背包的物品价值最大化，我们知道用贪心是不行的！
所以接下来开始动规：
首先定义状态dp[i][j]以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值，那么i=1的时候，放入的是物品1，这时候肯定是最优的啦！
那考虑一下j，j是当前容量，如果j<5，那么是不是就不能放，dp[1]j=0；那如果j>5，就可以放了，dp[1]j=20；
接着i=2放两个物品，求的就是dp[2][j]了，当j<5的时候，是不是同样的dp[2]j等于0；那当j<6是不是还是放不下第二个，只能放第一个；
那j>6呢？是不是就可以放第二个了呢？是可以，但是明显不是最优的，用脑子想了一下，发现dp[2]j=20，这个20怎么来的呢，当然是从前一个状态来的（注意这里就可以分为两种情况了）：一种是选择第二个物品放入，另一种还是选择前面的物品；
让我们假设一下j=10吧，可能会比较好理解！这时候：dp[2][10] = max(dp[1][10-w[2]])+v[2]，dp[1][10])；
dp[2][10] = max(dp[1][4])+10，dp[1][10])；
是不是很明显了呢，dp[1][4])+10是选择了第二个，于是容量相应就减少成4，之前已经得出dp[1][4]=0，就是说选了物品2，物品1就选不了了；dp[1][10]是不选择第二个，只选择第一个dp[1][10]是等于20的，于是得出dp[2][10]=20；
到这里就可以了，依次类推，动态转移方程为：dp[i][j] = max(dp[i-1][j-w[i]])+v[i]，dp[i-1][j])；
但是好像还有一些问题没考虑完.........
物品编号： 1 2 3
物品重量： 5 6 4
物品价值：20 10 12
我们知道dp[1]j=20，dp[2]j的时候是多少呢？我们看到动态转移方程并没有考虑j<w[i]的情况，但是我们可以加进去，由于dp[2][5]我们看出来是等于5的，为什么？因为不能选第二个，只能选第一个，所以.....dp[2][5]是不是刚好等于dp[1][5]了呢！所以当j<w[i]的时候，dp[i][j] = dp[i-1][j]就好了，是不是很神奇呢！

看起来这段文字讲的很透彻，那我们试试解决采药问题……