这周主要就新学习了DP的一些基础知识，看了一些例题，怎么用DP及应用到具体题目上，看的过程中，思路一次次被开创，虽然有的题目到现在还没有很清楚，但看过的很多题目也为我打开了一些新的思维。
首先，最开始接触到DP的时候就有一种感觉，这个跟求单源最短路径问题的Dijkstra算法想法好像，就每一步的状态都是当前最好的状态，不同的是求单源最短路径可能不是一维的，而我现在看到的DP差不多都是一维的，但由于学习了Dijkstra，理解起DP来也容易了好多。
应用动态规划来解决问题的时候，需要注意：
1、判断问题是否具有最优子结构性质，若不具备则不能用动态规划。
2、把问题分成若干个子问题（分阶段）。
3、建立状态转移方程（递推公式）。
4、找出边界条件。
5、将已知边界值带入方程。
6、递推求解。
就写几个看到的题目的方法思想，以及一些代码批注...
吃金币游戏小明写了一个简单的吃金币游戏，规则如下：
在一个长方形地图上，玩家每次能从一个方格走到相邻一个方格。
玩家控制的角色可以向下或者向右走，但不能向上或向左走。每个方格上都有一定的金币。
现在，小明想请你帮他想一个策略，尽可能多的获得金币（从左上角走到右下角可能获得的最大金币数）。
//用dp[a][b]表示到达当前点所能吃到的最大金币数 //那每一次的dp[a][b]如何来求呢？用的是下面的递推公式： dp[a][b]=max(dp[a-1][b],dp[a][b-1])+Coin[a][b] //由于每一步只能向右或向下走，所以每一点只能由上面和左边的点递推而来 //上就是dp[a-1][b]，左就是dp[a][b-1]，比较两个数的最大值加上当前点的金币数，就是到达当前点 //所能迟到的最大金币数了，最后dp[m][n]就是题目所求
一个数的序列bi，当b1 < b2 < ... < bS 的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ...
比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
int b[MAX_N + 10]; //记录总的序列中的数值
int aMaxLen[MAX_N + 10]; //记录以每个数为结尾的最长上升子序列
int main()
{
int i, j, N;
scanf("%d", & N); //序列长度
for( i = 1;i <= N;i ++ )
scanf("%d", & b[i]); //输入序列中的值
aMaxLen[1] = 1; //初始化 以第一个元素为结尾端点的最长上升子序列长度就是1
for( i = 2; i <= N; i ++ )
{
int nTmp = 0; //记录第i 个数左边子序列最大长度
for( j = 1; j < i; j ++ )
{ //搜索以第i 个数左边数为终点的最长上升子序列长度
//就是看当前第i个数之前的数中分别以他们为结尾端点的最长上升子序列的长度 找出最大值
if( b[i] > b[j] ) //首先要确保当前这个数i能跟前面的数呈上升趋势 大于
{
if( nTmp < aMaxLen[j] )
nTmp = aMaxLen[j];
}
}
aMaxLen[i] = nTmp + 1; //这样每一次循环来确定到每一个点的时候的最大上升子序列 当然如果b[i]比前面的数都要小 也就更新不了ntmp 最长上升子序列就是默认值0了
}
int nMax = -1;
for( i = 1;i <= N;i ++ )
if( nMax < aMaxLen[i])
nMax = aMaxLen[i]; //最后比较出以每一个数结尾的最长上升子序列中长度最长的即为题目所求
printf("%dn", nMax);
return 0;
}
给定 N (1 <= N <= 100) 和一个 N * N 的矩阵，求该矩阵的一个子矩阵，使得子矩阵中所有数字的和最大。求出这个最大值。
#include#include #include #define N 103 //把每一个从i行到j行的每一列相加 得到一个一条线的一维数组 int fun(int b[N], int n) { int i, max, c; c = 0; max = 0; for(i=1; i<=n; i++) { if(c > 0) //只要之前的和是正的就继续加下面的 如果负数肯定没有下一个单独是正的大 所以负数就让下一个整数单独开始 c = c+b[i]; //就像题目给的测试数据一样 哪怕中间有一个数是负数但是后面加的是正数 最后的和依然在不断递增 就是只要和为正就不断递增就行 else c = b[i]; if(max < c) //之前的最大和加上新的b[k]与之前的最大和比较 大就更新 不大就不更新 max = c; } return max; } int main() { int i, j, n, max, sum, k; int a[N][N], b[N]; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d", &a[i][j]); max = 0; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) //这里的j代表列 就是合并的每一列的列 b[j] = 0; //让每一列初始化和都为0 for(j=i;j <=n; j++) //这里是从i行到第j行所构成的矩阵 { for(k=1; k<=n; k++) //k管的是列数的向下推进 b[k]+=a[j][k]; //总体上b[k]存放的是从第i行到当前的第j行每一列的和 sum = fun(b, n); if(max < sum) max = sum; } } printf("%dn", max); return 0; }
给定n（1 <= n <= 500）个硬币，每个硬币都有面值，求每个能构成和为k（1 <= k <= 500）的硬币组合中，任意个数相互求和的总额种类，然后将所有硬币组合中最后得到的结果输出。
如果枚举到的硬币面值为 t ，存在dp[ i - t ] [ j ] = true，那么： 1、dp[ i ] [ j ] = true; 相当于总额里增加一个 t 的面值的硬币，但实际组成 j 的额度时并没有用到它。 2、dp[ i ] [ j + t ] = true; 相当于总额里增加一个 t 的面值的硬币，并且用它构成了新达到的额度 j + t。 初始化dp[ 0 ] [ 0 ] = true; 总额为 0 时，能构成 0 额度。 为了防止二次利用此硬币，总额需从 k 递减至 t。 这道题dp存放的不是答案而是状态
