动态规划：对解最优问题的一种途径、一种方法，而不是一种特殊算法
经典例题：数字金字塔 题意：金字塔第一层有1个含数字的点，第二层有两个含数字的点……第n层有n个含数字的点，求从n层的任意一点还是，到达第一层所经过的数字和最大为几？例如下图，n=3。 样例输入： 3 12 25 19 6 10 3 很明显，这是道dp水题
我们先定义一个二维数组dp[][]和a[][]，dp[i][j]表示从dp[1][1]到dp[i][j]的最大数字和，a[i][j]存储各个位置上的数值。 并且规定从(1,1)开始，只能向左下或者右下运动。 注意的几点： 1.左下：最后一步为从(i-1,j)走到(i,j)，得出规律：如果向左下走，dp[i][j]=dp[i-1][j]+a[i][j]； 2.右下:最后一步为从(i-1,j-1)走到(i,j)，得出规律：如果向右下走，dp[i][j]=dp[i-1][j-1]+a[i][j]； 3.很明显dp[i][j]需要一个值，根据定义，我们将a[i][j]赋给dp[i][j]；注意1和2图例：
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 从(1,1)走到左下角的(2,1)，也就是从(i-1,j)到(i,j) 从(1,1)走到右下角的(2,2)，也就是从(i-1,j-1)到(i,j)代码：
#include <cstdio> #include <algorithm> //#include <bits/stdc++.h> using namespace std; int a[1005][1005],dp[1005][1005],n;//数组开多大根据题目来 int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); } } dp[1][1]=a[1][1];//!注意！ for(int i=2;i<=n;i++) { for(int j=1;j<=i;j++) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; } } int x=0; /* 因为最后的数值存在dp[n][]里面，所以需要一个变量求出最大的数据 */ for(int i=1;i<=n;i++) { x=max(x,dp[n][i]); } printf("%d",x); return 0; } //结束这就是动态规划的基本题，dp数塔，最经典的dp。 其他更难的dp题目，详见洛谷题库
背包的基本：01背包
题目描述(这是我们老师上课给我们的奇葩描述) 你是一名小偷，现在你要去商店里偷东西(好孩子不能偷东西~) 因为动作匆忙，你只带了一个容量为V公斤的背包 商店里有m个商品，每件商品的价值为c[i]，重量为v[i]。 求背包最多能装的物品的价值最大是多少？ 输入：第一行输入V和n，第2~n+1行，每行输入c[i]和v[i] 输出：之前说过 样例输入： 4 10 1 2 3 3 5 4 9 7 样例输出： 12 思路： 变量dp[][]的用法与数塔类似，不再赘述。 现在我们来想一下第i件物品的情况。第i件物品有“放”和“不放”两种情况。 假如“不放”，问题便和第i件物品无关，只和前i-1件物品有关 假如“放”，那么背包容积至少会变成“V-v[i]”。 此时的最大价值那就很容易得出：dp[i][j]=dp[i-1][j-v[i]]+…… 根据之前动态规划的方法可知，省略号处应该填"a[i][j]"也就是这里的“c[i]” 至于为什么是i-1……动规里已经讲得很清楚了。上面的方法是用二维数组做的，那么，能不能用一位数组做呢？？？ 答案是肯定的
二维数组的思路肯定需要一重循环是这样的：dp[i][0……V]，但可以优化，使循环后的dp[v]就是原本的dp[i][v]。 很容易想明白，我们只要让V从V到0循环，问题就迎刃而解CODE
//一位数组做法 #include <bits/stdc++.h> using namespace std; int main() { //freopen("in2.txt","r",stdin); //freopen("out2.txt","w",stdout); int n,V,c[101],v[101],dp[500]={0}; scanf("%d%d",&n,&V); for(int i=1;i<=n;i++) { scanf("%d%d",&c[i],&v[i]); } for(int i=1;i<=n;i++) { for(int j=V;j>=v[i];j--) { dp[j]=max(dp[j],dp[j-v[i]]+c[i]); } } printf("%d",dp[V]); }结束 END
