动态规划基本概念

动态规划和分治法

分治法是将问题划分为不相交的子问题,递归的求解子问题,在将它们的解组合起来,求出原问题的解.动态规划应用于子问题重叠的情况,子问题具有公共的子问题. 在这种情况下,分治法会做许多不必要的工作.分治法会重复的求那些公共子问题,而动态规划只对那些问题求解一次,将解存储在数组中,从而避免重复求解.

动态规划常用于处理最优化问题

这种问题可以有很多可行的解,我们希望找到最优的值(最小值,最大值) 可能有多组最优解问题的形式类似于:有多少种方案? 最大值是多少?最少要删除多少个元素?

动态规划和分治法的基本策略

分治法 把规模为n的问题分解为相同的,规模小的子问题,分别求解,最后将子问题的解合并得到原问题的解. 典型的算法有:二分查找,归并排序,快速排序自顶而下的求解动态规划 根据简单易知的子问题的解,通过状态转移得到父问题的解,自底而上的求出原问题的解 动态规划仔细安排求解顺序,对每个子问题值求解一次,并将结果保存下来,付出额外的空间大大降低了时间的消耗关键在于状态和状态转移方程的确定

钢条切割问题

问题描述: 给定一根长为n的钢条,钢厂对这根钢条无成本的切割,不同长度的钢条有不同的售价,长度为i的钢条售价为pi.问:切割一个长为n的钢条,最多能售多少钱?

如果采取分治法,自顶向下

T(n) = T(i) + T(n-i) i\in(0,n)

时间复杂度是指数级,子问题被重复很多次计算,bad

动态规划,自底向上

用d[i] 存储 长度为i的钢条切割后能得到的最高利润 初始条件d[1] = p1状态转移: d[i] = max(d[i] , d[j] + d[ i-j ]) j\in(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)

转载于:https://www.cnblogs.com/star-and-me/p/8612789.html