数字三角形
本文最后更新于 205 天前,其中的信息可能已经有所发展或是发生改变。

数字三角形

 5从键盘输入 代表有5行数据
7
3 8 
8 1 0
2 7 4 4
4 5 2 6 5

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过 1。

分析:

这个就是典型的动态规划基础,那么动态规划是什么呢,如果你对动态规划这个概念很陌生,可以去看看其他文章,有递推标签的文章,这是动态规划的基础。我来介绍一下什么是动态规划。

 

 动态规划(Dynamic Programming)在数学上属于运筹学的一个分支,是求解决策过程 (decision process)最优化的数学方法,
同时也是计算机科学与技术领域中一种常见的算法思想。动态规划算法与我们前面提及的分治算法相似,
都是通过组合子问题的解来求解原问题的解。但是两者之间也有很大区别:
分治法将问题划分为互不相交的子问题,递归的求解子问题,再将他们的解组合起来求解原问题的解;与之相反,
动态规划应用于子问题相互重叠的情况,在这种情况下,分治法还是会做很多重复的不必要的工作,
他会反复求解那些公共的子问题,而动态规划算法则对相同的每个子问题只会求解一次,
将其结果保存起来,避免一些不必要的计算工作。

               进击的巨人里面团长说了一句话,我觉得很像动态规划,他说,只有当一个选择成为下一个选择的依据的时候,这个选择才有意义。边走边看,边算边走,运筹帷幄,我想这就是动态规划。

 

  • 最优子结构 : 即是局部最优解能够决定全局最优解(也可以认为是问题可以被分解为子问题来解决),如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质.
  • 子问题重叠 : 即是当使用递归进行自顶向下的求解时,每次产生的子问题不总是新的问题,而是已经被重复计算过的问题.动态规划利用了这种性质,使用一个集合将已经计算过的结果放入其中,当再次遇见重复的问题时,只需要从集合中取出对应的结果.

 动态规划百度百科  ,点击一下,可清晰的了解其意义。我个人认为,在算法当中,我最怕的就是这类题目,非常吃脑力,这类问题有几个经典问题,我收集了网上的资料,整理了一些经典问题,你们要是感兴趣,尝试的去做做,我已经对这类题目完全 失去斗志了!

 斐波那契数列问题及其相关变形
 最大连续子序列和问题及其相关变形
 最长递增子序列.....
 最长公共子序列.....
  .......
 背包问题
 线性动态规划
  .....等等
  如果感兴趣,可以去刷题网站试试!

这类问题容易与搜索回溯。,记忆化搜索问题搞混淆。

接下来来看看数字三角形这个解答吧!(个人接触的第一个动态规划的题目,认为这道题还是比较难的(我当时软件工程导论的课我都没听,全用来思考这题代码的逻辑和思路的),但是现在,我解决它还是绰绰有余的)


public class Test3 {
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         //在此输入您的代码...
         int n=scan.nextInt();
         int number[][]=new int [n][n];
         for(int i=0;i<n;i++){
             for(int j=0;j<=i;j++){
                 number[i][j]=scan.nextInt();
            }
        }
         int dp[][]=new int [n][n];
         dp[0][0]=number[0][0];
         for(int i=1;i<n;i++){
             for(int j=0;j<=i;j++){
                 if(j==0){
                     dp[i][j]=number[i][j]+dp[i-1][j];
                }//在三角形左边直角边由于没有左上角数据,所以要分类讨论
                 else{
                     if(i==j){
                         dp[i][j]=number[i][j]+dp[i-1][j-1];//在三角形斜边数据同理
                    }
                     else{
 
                         dp[i][j]=number[i][j]+Math.max(dp[i-1][j],dp[i-1][j-1]);
                    }
                }
            }
        }
         //因为向左或者向右的步数不能超过一,答案一定在最后一行的中间
         if(n%2==1)  System.out.println(dp[n-1][n/2]);//奇数情况下
         else System.out.println(Math.max(dp[n-1][n/2],dp[n-1][n/2-1]));//
         //如果题目没有给出向左向右步数相差一,照常输出最大值的那个就行了,在最后一行
    }}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇