动态规划基本概念
动态规划和分治法
- 分治法是将问题划分为不相交的子问题,递归的求解子问题,在将它们的解组合起来,求出原问题的解.
- 动态规划应用于子问题重叠的情况,子问题具有公共的子问题.
- 在这种情况下,分治法会做许多不必要的工作.
- 分治法会重复的求那些公共子问题,而动态规划只对那些问题求解一次,将解存储在数组中,从而避免重复求解.
动态规划常用于处理最优化问题
- 这种问题可以有很多可行的解,我们希望找到最优的值(最小值,最大值)
- 可能有多组最优解
- 问题的形式类似于:有多少种方案? 最大值是多少?最少要删除多少个元素?
动态规划和分治法的基本策略
- 分治法 把规模为n的问题分解为相同的,规模小的子问题,分别求解,最后将子问题的解合并得到原问题的解.
- 典型的算法有:二分查找,归并排序,快速排序
- 自顶而下的求解
- 动态规划 根据简单易知的子问题的解,通过状态转移得到父问题的解,自底而上的求出原问题的解
- 动态规划仔细安排求解顺序,对每个子问题值求解一次,并将结果保存下来,付出额外的空间大大降低了时间的消耗
- 关键在于状态和状态转移方程的确定
钢条切割问题
问题描述: 给定一根长为n的钢条,钢厂对这根钢条无成本的切割,不同长度的钢条有不同的售价,长度为i的钢条售价为pi.问:切割一个长为n的钢条,最多能售多少钱?
如果采取分治法,自顶向下
T(n) = T(i) + T(n-i) iin(0,n)
时间复杂度是指数级,子问题被重复很多次计算,bad
动态规划,自底向上
- 用d[i] 存储 长度为i的钢条切割后能得到的最高利润
- 初始条件d[1] = p1
- 状态转移:
d[i] = max(d[i] , d[j] + d[ i-j ]) jin(0,i)
- 长度为i 的钢条得到的最高利润 = 长度为j的钢条的最高利润 + 长度为 i-j 的钢条的最高利润
- 时间复杂度: i 从1到n , j从1到i O(n^2)
memset(d,-1,sizeof(d);
d[1] = p[1];
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
d[i] = max(d[i] , d[i-j]);
cout<<d[n]<<endl;
动态规划划分子问题未必只关注问题规模
应该首先关注哪些状态发生了转移
n个数围成一圈,一个指针初始状态指向1号,每次指针指向当前位置的旁边(左转和右转) , 问转动m次后回到1号的前提下,共有多少种转法?
- 指针只会转到旁边的两个位置
- 每次转动一次
- 初始时指针指向1号
- 转动一次,指针指向2号或者n号,转动次数+1
状态选择转动次数和指针位置
d[i][j]表示转动i次指向j的方法数目
状态转移方程
d[i][j] = d[i-1][j+1] + d[i-1][j-1]
- 稍微注意下边界,问题就解决了.时间复杂度O(n^2)