没学过动态规划的可以从先看看这篇博客，从“数字三角形”为例介绍dp基础：http://blog.csdn.net/baidu_28312631/article/details/47418773

 

 <li>

最长递增子序列

dp[i]表示a数组中以a[i]为结尾的最长递增子序列的长度

举例：

a[10]={5,6,4,8,3,7,1,2,9,10}

dp[10]={1,2,1,3,1,3,1,2,4,5}

 

状态转移方程：dp[i]=max(dp[j]+1,dp[i]) j=1,2,3…i-1

时间复杂度是o(n^2)。

核心代码：

    for (int i = 1; i <= n; i++) 
        {  
            dp[i] = 1;  
            for (int j = 1; j < i; j++) { if(a[i] > a[j]) 
                    dp[i] = max(dp[i], dp[j] + 1);  
            }  
        }  

 

 <li>

最长公共子序列

dpi表示a字符串匹配到第i个，b字符串匹配到第j个时此时的最长公共子序列长度

举例：a=abcd b=acde

dp        a     b     c     d

a          1     1     1     1

c          1     1     2     2

d          1     1     2     3

e          1     1     2     3

状态转移方程：

if(a[i-1]==b[j-1]) dpi=dpi-1+1;

else dpi=max(dpi-1,dpi)

时间复杂度：0(n*m)

核心代码：

 for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i-1] == b[j-1]) 
                    dp[i][j] = dp[i-1][j-1] + 1;

                else 
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

 

 <li>

0-1背包

有一个容积为V的背包，要将n件物品放入，每一件物品都有一定的体积和价值，求放入的物品的最大价值W

v[i]表示第i件物品的体积，

w[i]表示第i件物品的价值

dpi表示体积为i的背包能放入的物品(1-j)的最大价值

状态转移方程：dpi=max(dpi,dp[i-v[j]][j-1]+w[j]) j=1,2,3…n//也就是第j个物品放或不放

举例：

N=5

W[i]={1,2,3,4,5}

V[i]={3,2,4,1,5}

核心代码：

for(j=1;j<=n;j++)
{
    for(i=1;i<=v;i++) { if(i-v[j]>=0)<span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span>
        dp[i][j]=max(dp[i][j-1],dp[i-v[j]][j-1]+w[j]);
                else dp[i][j]=dp[i][j-1];
    }
}

空间复杂度为o(v*n)

还可以进行空间优化，是空间复杂度降低到o(v).

由于dp数组是从左往右更新的，如果直接将二维数组压缩至一维的话会出错，因为待比较的数据会被覆盖掉。

从左往右是完全背包的更新顺序（完全背包不限制每件物品的个数）

所以只能选择从右往左更新。（当然上面的代码也一样可以改成从右往左更新）

核心代码：

for(j=1;j<=n;j++) { for(i=v;i>=1;i--)
    {
                if(i-v[j]>=0)
        dp[i]=max(dp[i],dp[i-v[j]]+w[j]);
    }
}