动态规划算法，虽然有 如何学习动态规划算法， 但是依然很难理解。 动态规划算法的基本思想是解决将问题划分为子问题，而子问题之间不是相互独立，（如果独立可以使用分治法），即子问题之间存在公共子问题的情况，而动态规划算法中将这些子问题的解存起来，方便较大问题使用。
提到动态规划算法，又有一些其他概念，比如：最优解？自底向上？这时候改怎么理解呢？
首先看看几个典型的例子
（1）爬楼梯问题：一个人每次只能走一层楼梯或者两层楼梯，问走到第N层楼梯一共有多少种方法，参考 完整分析。
（2）找零个数最少问题： 现存在一堆面值为 V1、V2、V3 … 共N个单位的硬币，问最少需要多少个硬币才能找出总值为 T 个单位的零钱？假设这一堆面值分别为 1、2、5、21、25 元，需要找出总值 T 为 63 元的零钱。很明显，只要拿出 3 个 21 元的硬币就凑够了 63 元了，参考完整分析。
（3）01背包问题：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题，参考，完整分析。
对于动态规划算法难点在于找出公共子问题状态公式：
爬楼梯问题：爬楼梯中的状态在第N层，则人到第N层，必然是从第N-1层走一步上了，或是在第N-2层走两步上来。在P(N)为走到第N层楼梯的方法，显然P(N)=P(N-1)+P(N-2)
找零问题：要找出总值为T零钱的个数，是不是要找T-1个零钱的个数？NO！何来T-1？如果F(T)为找出T所需要的最少零钱个数，那么F(T)与F(T-1)有关么？要看最小单元是否为1，否则根本找不开。不一定哦，真正有关的，是F(T)与F(T-V1),F(T-V2),F(T-V3),……的关系， F(T)= Min(F(T-V1), F(T-V2),F(T-V3),…,F(T-VN))+1
01背包问题：进行决策，先抽象问题的解，当前的背包内的最大价值V，有物品的价值与背包的限制都有关系，应为二元函数，设V(i,j) 为前i件物品重量限制为j的最大价值，当将第i+1件物品拿进去的时候，考虑 如果Wi+1 > j, 则V(i,j) = V(i+1,j); 如果W(i+1)<j, 则或者将i+1放进去，则V(i+1,j)=Vi+1 + V(i, j-Wi), 或者，不将i+1放进去，则V(i+1,j)= V(i, j-Wi)， 则求两者之间的Max即为公共问题的解。
原文：http://blog.csdn.net/luoshenfu001/article/details/23289139