经典动态规划

      1.维基百科的描述:“动态规划(Dynamic Programming, DP)在查找有很多
重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问
题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划
保存递归时的结果,因而不会在解决同样的问题时花费时间 · · · · · · 动态规划只能应用于有最优
子结构的问题。优解能决定最优子结构的意思是局部最全局最优解(对有些问题这个要求并不能
完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。”


     2.通俗一点来讲,动态规划和其它遍历算法(如深/广度优先搜索)都是将原问题拆成多个子问
题然后求解,他们之间最本质的区别是,动态规划保存子问题的解,避免重复计算。解决动态规
划问题的关键是找到状态转移方程,这样我们可以通过计算和储存子问题的解来求解最终问题。
同时,我们也可以对动态规划进行空间压缩,起到节省空间消耗的效果。

        3.一些情况下,动态规划可以看成是带有状态记录(memoization)的优先搜索。状态记录的意思为,如果一个子问题在优先搜索时已经计算过一次,我们可以把它的结果储存下来,之后遍
历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的,即先解决子问题,再解
决父问题
;而用带有状态记录的优先搜索是自上而下的,即从父问题搜索到子问题,若重复搜索
到同一个子问题则进行状态记录,防止重复计算

如果题目需求的是最终状态,那么使用动态搜索比较方便;

如果题目需要输出所有的路径,那么使用带有状态记录的优先搜索会比较方便。

第一个简单动态规划题:求上n个台阶共几种方式(LC70题)

class Solution{
    public int climbStairs(int n){
        int[]dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议