动态规划是解决一类包含了状态转化和状态转移关系，具有最优子问题性质的，求取状态参量的确定值或最优值的算法      动态规划，最简单的例子 o台阶问题 n某人上台阶，一次走1阶或者2阶 问从地面上至第n个台阶，共有多少种不同的走法？ 状态方程：f(n)=f(n-1)+f(n-2) 数列：1 1 2 3 5 8 13 21 34 55 89 144 233…… o程序： int a[n]={1,1}; for(int i=2;i<n;++i)a[i]=a[i-1]+a[i-2];    动态规划，基本框架   1.1.划分给定问题为若干不同的阶段，并且用统一的方式表示出每个阶段的状态。  2.2.按照某种无后效性的规则选择状态。 3.确定状态决策和转移，更新状态列表。 4.3.是否已经遍历了整个状态空间？是则终止，否则转向步骤2 5.4.至此，状态列表中保存了所有的最优子问题的解。  

评论