专栏首页孟君的编程札记[动态规划] 数字三角形问题(一维数组实现)

[动态规划] 数字三角形问题(一维数组实现)

数字三角形问题:

一个数字三角宝塔。设数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层,每一步可沿左斜线向下右斜线向下走。假设三角形行数小于等于100编程求解从最顶层走到最底层的一条路径,使得沿着该路径所经过的数字的总和最大,输出最大值。 例如一个行数为5的三角形如下:

               7
             3   8
           8   1   0
         2   7   7   4
       5   5   2   6   5

这一个问题,很容易想到用枚举的方法去解决,即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和,这一想法很直观,也比较容易实现。不过,缺点是:当行数很大时,比如行数等于100,其枚举量是相当巨大的。

这是一个多阶段决策性的问题--> 最优路径上的每一个数字开始的向下的路径也是该数字到最下层的最优路径,符合最优化原理,可以考虑用动态规划的方法实现。

本文采用一维数组去求解数字三角形问题,并用上述行数为5的三角形作为实例来求解。

/** 
 *  
 * @author Eric 
 * 
 */  
public class TriangleProblem {  
  
    /** 
     * 使用一维数组结合动态规划思想求解数字三角形问题。
     * @param array 存储三角形数字的一维数组(从上到下,从左到右存储) 
     * @param n 数字三角形的行数 
     * @return 返回一个经过路径的数字的总和最大值 
     */  
    public int populateMaxSum(int[] array, int n) {  
        int[] result = new int[array.length];  
          
        for (int row = 0; row < n; row++) {  
            if (row == 0) {  
                /* 
                 * 设置定点的值  
                 */  
                result[0] = array[0];  
            } else {  
                int rowStartIndex = populateStartRowIndex(row);  
                  
                /* 
                 * 设置第row行第一个位置到顶点的最大值只有一个。
                 * 直接赋值。
                 */  
                result[rowStartIndex] = array[rowStartIndex]  
                        + result[rowStartIndex - row];  
  
                for (int col = 1; col <= row; col++) {  
                      
                    if (col < row) {  
                        /* 
                         * 处理到顶点的数值有两个节点的位置, 
                         * 取大的那一个。
                         */  
                        result[rowStartIndex + col] = max(result[rowStartIndex  
                                - row + col - 1]  
                                + array[rowStartIndex + col],  
                                array[rowStartIndex + col]  
                                        + result[rowStartIndex - row + col]);  
                    } else {  
                          
                        /* 
                         * 每行最右边的的位置到顶点的最大值也只有一个。
                         * 此时 row == col 
                         * 直接赋值。
                         */  
                        result[rowStartIndex + col] = result[rowStartIndex  
                                - row + col - 1]  
                                + array[rowStartIndex + col];  
                    }  
  
                }  
            }  
        }  
        /* 
         * 当所有的位置到顶点的位置都计算出来之后, 
         * 要计算出最大值,只要计算最大行中最大值即可。
         *  
         */  
        return max(populateStartRowIndex(n - 1), result);  
    }  
  
    /** 
     * 根据一个指定的行号,计算出在一维数组中对应的下标,最为该行的起始下标 
     * @param row 行号(从0开始) 
     * @return 
     */  
    private int populateStartRowIndex(int row) {  
        int sum = 0;  
        for (int i = 0; i <= row; i++) {  
            sum += i;  
        }  
        return sum;  
    }  
  
    private int max(int startIndex, int[] array) {  
        int max = array[startIndex];  
  
        for (int i = startIndex; i < array.length; i++) {  
            if (array[i] > max) {  
                max = array[i];  
            }  
  
        }  
        return max;  
    }  
  
    private int max(int v1, int v2) {  
        return (v1 > v2) ? v1 : v2;  
    }  
}

测试代码==>

public class Main {  
  
    public static void main(String[] args) {  
        TriangleProblem tp = new TriangleProblem();  
        int[] array = { 7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5 };  
        System.out.printf("最大和为 SUM=%d", tp.populateMaxSum(array, 5));  
    }  
}

输出结果==>

最大和为 SUM=30

当然,我们可以将三角形中的数据保存到文件中,然后读取文件的内容,再将这些数字初始化到一维数组中去,这里就不再展开。

比如,将三角形数据存在到一个txt文件中,数字之间用空格隔开:

7
3 8
8 1 0
2 7 7 4
5 5 2 6 5
... ...

本文分享自微信公众号 - 孟君的编程札记(gh_0f0f5e0ae1de),作者:孟君

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

原始发表时间:2019-10-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数独终盘生成的几种方法

    为了完成矩阵的转换,我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成:

    孟君
  • 一步步完成Maven+Spring+Dubbo+Zookeeper的整合示例

    本文给出一个整合Maven+Spring+Dubbo+Zookeeper的示例,并且一步步给出完成步骤,并对其中可能遇到的问题进行解决。

    孟君
  • 一步步完成Maven+SpringMVC+SpringFox+Swagger整合示例

    本文给出一个整合Maven+SpringMVC+SpringFOX+Swagger的示例,并且一步步给出完成步骤。

    孟君
  • Spring Boot2(四):使用Spring Boot实现多数据源过程

    实际业务场景中,不可能只有一个库,所以就有了分库分表,多数据源的出现。实现了读写分离,主库负责增改删,从库负责查询。这篇文章将实现Spring Boot如何实现...

    鸟不拉屎
  • C++随笔(二)用指针强制访问private的值

    private本来是私有变量,外部无法访问的,但是抖个机灵,我们用指向类的指针和在类里面不断偏移我们的指针地址来访问私有成员变量的值。

    Pulsar-V
  • <>并归排序&&小和问题&&逆序对问题

    master公式(也称主方法)是用来利用分治策略来解决问题经常使用的时间复杂度的分析方法,(补充:分治策略的递归解法还有两个常用的方法叫做代入法和递归树法,以后...

    大学里的混子
  • <>快速排序&&荷兰国旗&&

    小于区域推着等于区域往右跑,但是等于区域与大于区域之间有一个待定的区域,所以array[cur]< num时候cur++,所以array[cur] > num...

    大学里的混子
  • 乘法表中第k小的数

    给定高度m 、宽度n 的一张 m * n的乘法表,以及正整数k,你需要返回表中第k 小的数字。

    你的益达
  • 深度学习系列 | 知识库上的问答系统:实体、文本及系统观点

    编者:本文来自复旦大学博士崔万云在携程技术中心主办的深度学习Meetup上的主题演讲,分享了复旦大学研发的基于知识图谱的QA系统。戳上面的“携程技术中心”(ct...

    携程技术
  • [剑指offer][Java]调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位...

    后端技术漫谈

扫码关注云+社区

领取腾讯云代金券