专栏首页每天学Java理解动态规划

理解动态规划

直到现在个人还是觉得动态规划是挺难理解和做题的,所以这一篇文章不去引用很多的概念,就仅仅谈一谈自己对于动态规划的理解,以及做题的思路

动态规划

我们小时候上学的时候,从家到学校的方案应该有多种,假如某一天你想知道走哪一条路最快到学校,走哪一条路最慢,走哪一条路风景最好,该怎么办呢?

路线图如下,A是家,H是学校。其中BCDEFG属于超市,池塘等地方。假设我们现在想知道哪条路线最快到学校,防止以后起床晚了不知道走哪条路。

   D----E----
  /      \    \
 /        \    \
A---->B----F----H
 \   /     /    /
  \ /     /    /
   C----G-----

其实知道哪个最快,最简单的方案就是都走一遍就知道了,一共要走的路线方案如下:

方案一:A->D->E->H
方案二:A->D->E->F->H
方案三:A->B->F->H
方案四:A->C->G->F->H
方案五:A->C->B->F->H
方案六:A->C->G->H

如果我们每次都是在A开始计时,到H结束计时,那么各个路线哪个时间短,哪个就最快,也就达到我们的目标。这种方案我们叫做穷举法。

但是各位看官,我们审视一下上面的路线,A->C我们是不是走了三次,A->D走了两次,D->E走了两次,C->G走了两次,F-H走了三次。作为了一个懒人,如果我们在上面方案二走过F->H之后,你测试方案三/方案四的时候,你走到F,你还想走到H吗?肯定不想啊,刚走过,又要走, 我们就是为了偷懒才找最短路线的,现在找最短路线竟然不偷懒,这怎么说的过去。

所以,懒人的我们改变了策略,计时不从头到尾,每到一个地方我就结束计时,这样我第一次走过F->H就知道F->H要耗时,那么我在走方案三的时候 F->H就不走了,因为我已经记录F->H需要多久。这种方案我理解就是动态规划,把已经走过的地方存储下来,然后找到相应的规律就可以推导出最优的方案。

看完这,我们看看动态规划的专业解释

基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多, 有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算, 节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式

状态转移方程

状态转移方程,是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第K阶段的状态Sk以及决策uk(Sk),则第K+1阶段的状态Sk+1也就完全确定, 一般来说,状态转移方程是我们实现动态规划最难的一步。

适用条件

任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言, 余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

2.无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

3.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中, 不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。

看完这些我们来看一个例子,学习一下动态规划解决实际问题

数字三角形

              1               第一层
          2       3           第二层
      11     10       12      第三层
   9      7      15       24  第四层 

在上面的数字三角形中寻找一条从顶部(第一层)到底边的路径,使得路径上所经过的数字之和最小。

个人有两种方案一种从第一层到第四层寻找最优解,一种是第四层往第一层最优解。

方案一:

路径上的每一步都只能往左下或 右下走也就是 2 只能到11和10,3只能到10和12。

这跟我们第一部分找最省时的例子相似,可以采用穷举法去搞定,但是有很多无效的路程(已经走过)。

这里我们使用dp[i][j]表明某i+1层,第j+1位数到达底部的之和(案例中的计时)。

那么我们看

d[0][0]=1

d[1][0] = 2 d[1][1] =3

d[2][0] = 13 d[2][1]=(d[1][0] 和 d[1][1]最小值) +d[2][1]

......

我们会发现,后面每一个位置对应的最小值,都是上一层中可到达该位置的最小值加上该位置大小本身,于是得到状态转移方程

d[i][j] = d[i][j]; i=0,j=0 d[i][j] = d[i-1][j]+d[i][j]; i!=0,j=0 d[i][j] = d[i-1][j-1]+d[i][j]; i=j d[i][j] = min{d[i-1][j-1],d[i-1][j]}+d[i][j];i>1,j>1

方案二:

我们初始化第四层,然后从第三层依次往上取:

d[3][0] = 9 d[3][1] = 7 d[3][2] =15 d[3][3] = 24

d[2][0] = min{d[3][0],d[3][1]}+d[2][0]

......

得到状态转移方程为:

d[i][j] = min{d[i+1][j],d[i+1][j+1]}+d[i][j]

看完公式,我们写代码就简单了。

实现代码(C++)

//
//  main.cpp
//  TheTriangle
//
//  Created by 陈龙
//  Copyright © 2019 陈龙. All rights reserved.
//

#include <iostream>
using namespace std;

bool cmp(int a,int b){
    return a<b;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int N;
    cin>>N;
    int dp[N][N];
    for (int i=0; i<N; i++) {
        for (int j=0; j<=i; j++) {
            cin>>dp[i][j];
//             cout<<" "<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }
    
    
    for (int i=1; i<N; i++) {
        for (int j=0; j<=i; j++) {
            if (j==0) {
                dp[i][j] = dp[i-1][j]+dp[i][j];
            }else if(i==j){
                dp[i][j] = dp[i-1][j-1]+dp[i][j];
            }else{
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j],cmp)+dp[i][j];
            }
        }
    }
    
    for (int i=0; i<N; i++) {
          for (int j=0; j<=i; j++) {
              cout<<dp[i][j]<<" ";
          }
         cout<<endl;
    }
    return 0;
}

/*
4
1
2 3
11 10 12
9 7 15 24
*/

本文分享自微信公众号 - 每天学Java(gh_fddfb9d03324),作者:每天学Java

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图的构建

    每天学Java
  • 高精度运算

    在写Java代码时候,我们其实很少去考虑高精度运算,即使遇到无法避免高精度的计算问题也不会太烦恼,因为有大整数类BigInteger以及BigDecimal工具...

    每天学Java
  • Java的即时编译

    “ 程序执行效率应该是每一位程序员都关注的地方,一般来说,程序执行效率一部分依靠程序员编写的代码,一部分依赖程序执行的平台,在Java中,虚拟机就是平台,如何让...

    每天学Java
  • 初学者接触web前端需要注意什么?避免走上弯路

    初学Web前端要注意什么?如何学好JS模块化编程?JavaScript是前端三要素之一,也是很多初学Web前端的人遭遇的第一条拦路虎。很多同学表示JavaScr...

    用户5827212
  • 个人小程序已经开放注册,你准备好了么?

    小程序在发布前引起了异常轰动,业界十分看好,课时发布至今,貌似没什么动静,使用率并不是很高,但是不要紧,小程序已经可以让个人开发者也来注册,只要你拥有一个个人公...

    风间影月
  • 1056 组合数的和 (15 分)

    给定 N 个非 0 的个位数字,用其中任意 2 个数字都可以组合成 1 个 2 位的数字。要求所有可能组合出来的 2 位数字的和。例如给定 2、5、8,则可以组...

    可爱见见
  • 烈火烧不尽的“恶性毒草”—— 摩诃草APT组织的攻击活动

    印度背景的APT组织代号为APT-C-09,又名摩诃草,白象,PatchWork, angOver,VICEROY TIGER,The Dropping Ele...

    用户1631416
  • FUSE(FileSystem in User Space) 对算法的价值

    MLSQL 有一段时间致力于融合大数据平台和算法平台,实现 【同一个平台,同一个语言。】。事实上我们通过各种方式做到了,通过整合Spark ML,Spark M...

    用户2936994
  • Python-练习6

    创建一个小游戏:       1). 游戏人物:    People            张琴成,男, 18岁,初始战斗值1000;            胡...

    py3study
  • 剑指offer 孩子们的游戏(圆圈中最后剩下的数)

    每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让...

    week

扫码关注云+社区

领取腾讯云代金券