注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

AP 计算机 数字三角形问题 递归,记忆化,动态规划算法实现  

2017-06-13 18:25:45|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
AP 计算机 数字三角形问题 递归,记忆化,动态规划算法实现 - 千里马 - 众里寻他千百度,名师成就满分路

AP 计算机 数字三角形问题 递归,记忆化,动态规划算法实现 - 千里马 - 众里寻他千百度,名师成就满分路

题目描述 Description

如图所示的数字三角形,从顶部出发,在每一结点可以选择向左走或得向右走,一直走到底层,要求找出一条路径,使路径上的值最大。

输入描述 Input Description

第一行是数塔层数N(1<=N<=100)。

第二行起,按数塔图形,有一个或多个的整数,表示该层节点的值,共有N行。

输出描述 Output Description

输出最大值。

样例输入 Sample Input

5

13

11 8

12 7 26

6 14 15 8

12 7 13 24 11

样例输出 Sample Output

86

 只要对该题稍加分析,就可以得出一个结论:
  如果得到一条由顶至底的某处的一条最佳路径,那么对于该路径上的每一个中间点来说,由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。
  我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看
作一个n-1个阶段的决策问题。从始点出发,依顺向求出第一阶段、第二阶段,……,第n-1
阶段中各决策点至始点的最佳路径,最终求出始点到终点的最佳路径。
用二维数组f[i][j]表示第i行的第j个数能得到的最大值,不难写出下列状态转移方程:
f[i][j]=max{f[i-1][j-1],f[i-1][j]}+map[i][j]//map为权值数组
但要注意的是,
每行第一个只能选择上一行的第一个,即:
f[i][1]=f[i-1][1]+map[i][1];
每行最后一个也只能选择上一行的最后一个,即:
f[i][i]=f[i-1][i-1]+map[i][i];

状态转移方程:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

import java.util.Arrays;


public class NumTriangle {
    public static final int N=5;
    public static int fun1(int[][] a,int x,int y)
    {
        int right,left;
        if(x==a.length-1)
            return a[x][y];
        left=fun1(a,x+1,y);
        right=fun1(a,x+1,y+1);
        if(left>right)
            return left+a[x][y];
        else
            return right+a[x][y];
    }
    public static int fun2(int[][] a,int x,int y)
    {
        if(x==a.length-1)
            return a[x][y];
        else
            return Math.max(fun2(a,x+1,y), fun2(a,x+1,y+1))+a[x][y];
    }
   
   
    public static int fun3(int[][] a,int x,int y)
    {
       int[][] b=new int[a.length][a.length];
       for(int r=0;r
           for(int c=0;c
               b[r][c]=-1;
  
       if(b[x][y]>=0)
           return b[x][y];
       if(x==a.length-1)
           return a[x][y];
        return b[x][y] = a[x][y] + Math.max(fun3(a,x+1,y), fun3(a,x+1, y+1)); //保存d[i][j]并返回
    }
   
    public static int fun4(int[][] a)
    {
        for(int i=a.length-1;i>=1;i--) 
        { 
            for(int j=0;j
            { 
                a[i-1][j]+=Math.max(a[i][j],a[i][j+1]); 
            } 
        }
        return a[0][0];
    }
    public static void main(String[] args) {
        int[][] a={{1,0,0,0,0},
                   {6,3,0,0,0},
                   {8,2,6,0,0},
                   {2,1,6,5,0},
                   {3,2,4,7,6}};
       
        System.out.println(fun3(a,0,0));
        System.out.println(fun4(a));
    }

}

AP 计算机 数字三角形问题 递归,记忆化,动态规划算法实现 - 千里马 - 众里寻他千百度,名师成就满分路

动规解题的一般思路

1、将原问题分解为子问题

  • 把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决(数字三角形例)
  • 子问题的解一旦求出就会被保存,所以每个子问题只需求解一次。

2、确定状态

在用动态规划解题时,我们往往将和子问题相关的各个变量的一组取值,称之为一个“状态”。一个“状态”对应于一个或多个子问题,所谓某个“状态”下的“值”,就是这个“状态”所对应的子问题的解。

3、确定一些初始状态(边界状态)的值

以“数字三角形”为例,初始状态就是底边数字,值就是底边数字值。

4、确定状态转移方程

定义出什么是“状态”,以及在该 “状态”下的“值”后,就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的“状态”,求出另一个“状态”的“值” 。状态的迁移可以用递推公式表示,此递推公式也可被称作“状态转移方程”。

能用动规解决的问题的特点

  1. 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质。
  2. 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。
俏也不争春,只把春来报.腾飞学子(深中部)平均4.92分,以93%的满分率(全美满分率26.6%), 以100%的优秀率享誉海内外,开创了中国AP计算机教学成功的先河,谱写了中国中学生在信息技术领域的华丽篇章.为中国AP计算机教学树立了典范,为中国更多跃跃欲试学子学习AP计算机树立了榜样,选修学生人数一年内由23人爆炸性增长120人,深受学生好评。
 
目前学生遍及美国费城,洛杉矶,旧金山,纽约,华盛顿,宾夕法尼亚,北卡罗纳州,新罕布什州,俄勒冈,北京,长春,重庆,南京,成都,济南,广州,深圳,台湾台中....  
  评论这张
 
阅读(24)| 评论(15)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017