动态规划经典问题
1、三角数塔问题
设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：
要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。
【代码】
//
// 例题1 三角数字塔问题 //
//
#include <stdio.h>
#include <stdlib.h>
#define MAXN 101
int n,d[MAXN][MAXN];
int a[MAXN][MAXN];[......]
c++常见的动态规划问题分析与求解.
动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（全面解析回溯法：算法框架与问题求解)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。
目录（点击跳转）
动态规划例题：数字三角形10.1 什么是动态规划
前面学过了用递归的方法解决问题。但是，单纯的递归，在解决某些问题的时候，效率
会很低。例如下面这道题目：
例题：数字三角形
问题描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路
径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求
出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。
输入数据[......]
今天在建模的时候又回头看了看自己的算法课本，真是温故而知新。这里，我主要想从树的角度来探讨一下这三类算法。
首先我想说的是，当你看到一个算法的时候，脑子里必须要有一个实例立马出现，这样才说明你对这个算法算是有点掌握，否则看到一个算法的时候，乱七八糟的算法一下子都出来了，那么说明你并没有很好的理解这些算法，而是把他们搅在一起了。
那么看到这三种算法，你应该有所出现：
贪心法是动态规划法的特例，如0-1背包，最小代价生成树（prim算法和cruskal算法），huffman算法，以及地杰斯特[......]
推理题：有人邀请A,B,C,D,E,F6个人参加一项会议，这6个人有些奇怪，因为他们有很多要求，已知：
1.A,B两人至少有1人参加会议。
2.A,E,F3人中有2人参加会议。
3.B和C两人一致决定，要么两人都去，要么两人都不去。
4.A,D两人中只1人参加会议。
5.C,D两人中也只要1人参加会议。
6.如果D不去，那么E也决定不去。那么最后究竟有哪几个人参加了会议呢？
……
推理题：有人邀请A,B,C,D,E,F6个人参加一项会议，这6个人有些奇怪，因为他们有很多要求，已知：
1.A,B两人至少有[......]
关于最大字段和，已有4中方法对其进行求解，现对其进行扩展，得到两个扩展的问题：
一、最大子矩阵问题
1、问题描述：给定一个m行n列的子矩阵A，试求出矩阵A的一个子矩阵，使其各元素之和为最大。
2、求解策略：对该问题，如果用穷举法求解，时间复杂度将为O(m2n2)，利用其为最大字段和问题的扩展，将其划归成最大字段和问题，然后再用最大字段和的最优方法进行求解，则可降低时间复杂到O(m2n) 。即先长度为m的维度上求出第i行到第j行每一个的元素和存储到一个n维的数组中，再对该数组进行最大字段和的动态规划法求解，求出结果。[......]
Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1217 Accepted Submission(s): 625
0013算法笔记——【动态规划】最大子段和问题，最大子矩阵和问题，最大m子段和问题.
1、最大子段和问题
问题定义：对于给定序列a1,a2,a3……an,寻找它的某个连续子段，使得其和最大。如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。
(1)枚举法求解
枚举法思路如下：
以a[0]开始: {a[0]}, {a[0],a[1]},{a[0],a[1],a[2]}……{a[0],a[1],……a[n]}共n个
以a[1]开始: {a[1]}, {a[1],a[2]},{a[1],a[2],a[3]}……{a[......]