精华内容
下载资源
问答
  • 数塔问题:设有一个三角形数塔(如下图所示),求自塔顶至塔底的一条路径,使得该路径上结点的值的总和最大。设计动态规划算法,并分析时间复杂性,C程序求自塔顶至塔底的一条路径,使得该路径上结点的值的总和最大。...
  • 动态规划算法数塔问题

    千次阅读 2019-05-11 09:52:16
    /* 3 12 56 23 4 78 34 69 34 19 12 3 54 12 34 */ ...思路:从最底层往上走,判断下层两个节点中的最大值, 并将最大值与上层节点中的值相加得到这一步的最大值, ...再与上上层的节点相加,再保存到新的塔中, 如...
    package cn.gldwolf.bigdata;
    
    /*
    3
    12  56
    23  4   78
    34  69  34  19
    12  3   54  12  34
    */
    
    /*
    思路:从最底层往上走,判断下层两个节点中的最大值,
    并将最大值与上层节点中的值相加得到这一步的最大值,
    将最大值保存到新的数塔中
    再判断上层节点的的两个节点的最大值,
    再与上上层的节点相加,再保存到新的数塔中,
    如此循环往复,最终得到顶层节点的值一定为最大值。
    
    输出路径时:
    将两个数塔相减,得到下一个节点的值,
    下一个节点的值的下标要么和上层节点的下标一致,
    要么为上层节点的下标 +1
    */
    
    import java.util.Scanner;
    
    public class NumberTower {
        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            System.out.print("Please input the tower height: ");
            int height = input.nextInt();
            int firIndex = height - 1; // 数组的长度
            int[][] orignal = new int[height][]; // 原始的数塔数组
            int[][] ultima = new int[height][]; // 求最大值以后的数塔数组
            System.out.println(orignal.length);
    
            System.out.println("Please input the number for the number tower: ");
            // 生成数塔数据
            for (int i = 0; i < orignal.length; i++) {
                orignal[i] = new int[i + 1];
                for (int j = 0; j <= i; j++) {
                    orignal[i][j] = input.nextInt();
                }
            }
    
            createUltimaArray(firIndex, orignal, ultima);
            printTrace(firIndex, orignal, ultima);
        }
    
        // 生成求完最大值后的数塔数组
        public static void createUltimaArray(int firIndex, int[][] orignal, int[][] ultima) {
    
            // 将原始数塔中的数据加载到 ultima 数塔中
            for (int i = 0; i < orignal.length; i++) {
                ultima[i] = new int[i + 1];
                for (int j = 0; j <= i; j++) {
                    ultima[i][j] = orignal[i][j];
                }
            }
    
            // 定义一个临时变量保存下层节点中两个值中的最大值
            int temp_max;
    
            // 判断下层两个节点中的最大值,并将最大值与节点中的原始数值相加并保存
            for (int i = firIndex - 1; i >= 0; --i) {
                for (int j = 0; j <= i; ++j) {
                    temp_max = Math.max(ultima[i + 1][j], ultima[i + 1][j + 1]);
                    ultima[i][j] = temp_max + orignal[i][j];
                }
            }
        }
    
        public static void printTrace(int firIndex, int[][] orignal, int[][] ultima) {
            int max = ultima[0][0];
            System.out.print(orignal[0][0]); // 第一个节点的值是确定的
            int j = 0; // 确定初始的二维下标,并提供后续控制  // 这个地方很关键
            // 循环判断
            for (int i = 1; i <= firIndex; i++) {
                // 用 ultima 数组和 orginal 数组相减,得到其子节点在 ultima 数组中的值
                int node = ultima[i - 1][j] - orignal[i - 1][j];
                // 因为对上层节点而言,其子节点只有两个,要么和它下标一致,要么为其下标 +1
                if (node != ultima[i][j])  // 判断,如果和它相同的下标不对,则对下层的下标 +1
                    ++j;
                System.out.print(" --> " + orignal[i][j]);
            }
        }
    }
    
    展开全文
  • /** File name : digital_tower.cpp* Function : 动态规划 数塔问题求解 C++实现* Created on : 2016年6月17日* Author : beijiwei@qq.com* Copyright : 欢迎大家和我一起交流学习,转载请保持源文件的完整性。...
    /** File name  : digital_tower.cpp* Function   : 动态规划 数塔问题求解  C++实现* Created on : 2016年6月17日* Author     : beijiwei@qq.com* Copyright  : 欢迎大家和我一起交流学习,转载请保持源文件的完整性。任何单位和个人不经本人允许不得用于商业用途      9    12 15   10 6 8  2 18 9  519 7 10 4 16从顶层或底层 走,在每一节点可选择左走或者右走.求一条路径,使得到的数值和最大.input:912 1510 6 82 18 9  519 7 10 4 16*/#include #include #pragma warning(disable:4996)using namespace std;#define M 5int get_max(int x, int y);int main(int argc, char** argv){    int i = 0, j = 0, k = 0;    int map[M][M];    int result[M][M];    freopen("input.txt", "r", stdin);    memset(result, 0, sizeof(int)*M*M);    memset(map, 0, sizeof(int)*M*M);    for (i = 0; i < M; i++)//读入塔    {        for (j = 0; j < i + 1; j++)        {            cin >> map[i][j];            if (i == M - 1)            {                result[i][j] = map[i][j];            }        }    }    for (k = M - 2; k >= 0; k--)//上塔 第k层,    {        for (i = 0; i < k + 1; i++)//统计 一行的每一个节点, 当前点是(k,i)        {            result[k][i] = get_max(map[k][i] + result[k + 1][i], map[k][i] + result[k + 1][i+1]);        }    }    cout << result[0][0] << endl;    int target = result[0][0] - map[0][0];    cout << map[0][0] << "\t"; //从塔顶至塔底 输出路径    i = 1;    while ( i y) ? x : y;} 原文作者:动态规划
    展开全文
  • 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化的算法思想 简单来说,动态规划将一个复杂的问题分解成若干个子问题,通过综合子问题的最优解来得到原问题的最优解。需要注意的是,动态规划会将每个...

    动态规划(Dynamic Programming,DP)是一种用来解决一类最优化的算法思想
    简单来说,动态规划将一个复杂的问题分解成若干个子问题,通过综合子问题的最优解来得到原问题的最优解。需要注意的是,动态规划会将每个求解过的子问题的解记录下来,这样当下一次碰到同样的子问题时,就可以直接使用之前记录的结果,而不是重复计算。

    需要注意:
    一个问题必须拥有重叠子问题和最优子结构,才能使用动态规划去解决。

    题目描述

    如下图所示,将一些数字排成数塔的形状,其中第一层有一个数字,第二层有两个数字……第n层有n个数字。现在要从第一层走到第n层,每次只能走向下一层连接的两个数字中的一个,问:最后将路径上所有数字相加后得到的和最大是多少?
    数塔问题

    输入:

    第行输入数塔的层数n
    剩下的n行输入每行的数字

    输出:

    第一行输出最大和
    第二行输出所选择的路径

    样例:
    输入:
    5
    5
    8 3
    12 7 16
    4 10 11 6
    9 5 3 9 4
    输出:
    44
    5->3->16->11->9
    

    解题思路:

    使用动态规划求解

    使用dp[i][j] 表示第 i 层第 j 个数字到数塔最底层的最大和,这样最后dp[1][1] 就表示最大和。

    下面为AC代码:

    /*
     * @Description: 动态规划求解数塔问题
     * @Author: 
     * @Date: 2020-05-02 10:54:40
     * @LastEditTime: 2020-05-02 11:11:53
     * @LastEditors: Please set LastEditors
     */
    #include <iostream>
    #include <algorithm>
    #include <math.h>
    #include<string>
    using namespace std;
    
    const int max_n = 1000;
    
    int f[max_n][max_n];  //表示输入的数塔
    int dp[max_n][max_n]; //dp[i][j]表示从第 i 层的第 j 个数字出发向下遍历到底层可以达到最大和。
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                cin >> f[i][j]; //输入数塔
            }
        }
        //考虑边界问题
        for (int i = 1; i <= n; i++)
        {
            dp[n][i] = f[n][i]; //最后一层的dp与数塔中的数字相同
        }
        //从第n-1层不断往上计算出dp[i][j],即自底向上
        for (int i = n - 1; i >= 1; i--)
        {
            for (int j = 1; j <= i; j++)
            {
            	//关键步骤
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
            }
        }
        cout << dp[1][1] << endl;
        //下面输出所选择的路径
        cout<<f[1][1];
        int j = 1;
        for(int i = 2;i <= n;i++){
            int temp = dp[i - 1][j] - f[i - 1][j];
            if(temp == dp[i][j + 1]){//如果temp == dp[i][j + 1] 则表示下一步应该选择 f[i][j + 1]
                j++;
            }
            cout<<"->"<<f[i][j];
        }
        system("pause");
        return 0;
    }
    

    运行结果:
    运行结果

    展开全文
  • [算法]动态规划解决数塔问题

    千次阅读 2019-04-30 09:47:00
    /*动态规划部分*/ for ( i = n - 2 ; i > 0 ; i -- ) { // 从倒数第二层到第一层 for ( j = 1 ; j i ; j ++ ) { // 从左到右遍历一层的所有元素 if ( r [ i + 1 ] [ j ] ...
    #include <iostream>
    
    using namespace std;
    const int N = 50;
    
    void dataTower(int data[][N], int n) {
        int r[n][N] = {0};// 每阶段路径计算结果
        int i, j;
        int path[n][N] = {0};// 下一步最优节点列坐标
        for (i = 1; i < n; i++)
            r[n - 1][i] = data[n - 1][i];// 最底层初始化
        /*动态规划部分*/
        for (i = n - 2; i > 0; i--) {// 从倒数第二层到第一层
            for (j = 1; j <= i; j++) {// 从左到右遍历一层的所有元素
                if (r[i + 1][j] > r[i + 1][j + 1]) {// 左下角元素>右下角元素
                    r[i][j] = r[i + 1][j] + data[i][j];
                    path[i][j] = 0;
                } else {
                    r[i][j] = r[i + 1][j + 1] + data[i][j];
                    path[i][j] = 1;
                }
            }
        }
        j = 1;
        cout << "The max value of the tower is :" << r[1][1] << endl;
        for (i = 1; i < n - 1; i++) {
            cout << data[i][j] << "--";
            j += path[i][j];
        }
        cout << data[i][j] << endl;
    
    
    }
    
    int main() {
        int data[][N] = {};
        int n;
        dataTower(data, n);
        return 0;
    }
    
    展开全文
  • 数塔问题: 描述:从数塔的顶层出发,在每一个节点可以选择左右方向,一直走到最底层。 求找出一条路径,使得路径上的数值和最大。 d[n][n] 数塔,三角矩阵 maxAdd[n][n] 存储动态规划每一步决策结果 path[n][n] ...
  • 动态规划数塔问题

    万次阅读 多人点赞 2015-05-17 23:35:59
    下面以一道经典的动态规划题目说明动态规划算法的思想,文末会官方的给出对动态规划的文字叙述。先看题目:如下图(图片来自百度图片)是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,...
  • 数字金字塔 题目描述 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。...所有的均非负的且不大于100。
  • 动态规划经典题目——数塔问题 ...
  • 动态规划算法数塔

    2020-05-02 15:50:42
    数塔从顶部出发,在每一结点可选择左下或右下走,一直走到底层,找出一条路径使数值最大 输入: 4 7 2 3 4 5 7 1 12 4 8 输出: 27 #include <bits/stdc++.h> using namespace std; int n,a[101][101]; int ...
  • //存储数塔的数组 int step[100][100];//记录步数的数组,即往哪个方向走 int calculatearr[100][100];//用于记录计算步数的数组 int layer;//层数 int k = 1;//这是用于输出层数时判断到第几层了 void manage()...
  • 动态规划数塔问题

    2019-03-24 11:29:23
    下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大. 算法实现: I. 首先利用一个二维数组data存储数塔的原始数据,然后利用一个中间...
  • 动态规划-数塔问题

    2020-03-31 21:05:06
    动态规划算法解决一些问题,算法的时间复杂度事比较低的。是一种用空间换时间的算法设计思想。 基本结构 F(n) A[0]=A[1]<-1 for i<-2 to n do 状态转移方程 return A[n] 基本思想 动态规划就是用一种类似...
  • JAVA算法数塔问题动态规划

    千次阅读 2018-01-27 23:34:51
    数塔问题(使用动态规划思路求解) 如图所示,给定一个正整数构成的三角形,如下所示: 在下面的数字三角形中寻找一条从顶部到底边的路径, 使得路径上所经过的数字之和最大。 路径上的每一步都只能往左下...
  • 首博今天尝试了一下动态规划思想的代码实现,选取了比较简单的数塔问题,下面展示的是写这个代码遇到的问题。(附有c++源程序)问题是这样的:有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,...
  • 动态规划主要针对优化问题。所谓规划就是“比较全面的长远的计划”。在动规的算法策略中,它体现在他的决策不是线性的,而是全面考虑各种不同的情况再分别进行决策,最后通过多阶段决策逐步找出问题的最终解。当各个...
  • 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? 已经告诉你了,这是个DP的题目,你能...
  • 动态规划DP
  • 数塔问题,简单的动态规划算法

    千次阅读 2009-04-27 13:58:00
    /*数塔问题:912 1510 6 82 18 9 519 7 10 4 16有形如图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。...在用动态规划考虑数塔问题时可
  • 数塔问题 图问题中的动态规划 多段图的最短路径问题 二级目录 二级目录 数塔问题 题意: 下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和...
  • [动态规划] 数塔问题

    千次阅读 2014-07-05 19:41:50
    这是一道简单的动态规划题,状态转移是自下向上的,算法思路: 假如路径经过第四层2,第五层一定选19 假如路径经过第四层18,第五层一定选10 假如路径经过第四层9,第五层一定选10 假如路径经过第四层5,第五层...
  • 后来才知道可以使用“动态规划”这种思想(或者叫算法范式)去解决这个问题。 但是看了一些鸡蛋问题动态规划的文章,依然只是流于形式,并不能理解其中的精髓。想想或许是鸡蛋问题对我现在而言难了一些,所以只好...
  • 接下来 用贪心算法动态规划 17 // 这里用了贪心算法,每一步算出每一行的最大值,最后得到总体最大 18 for ( int i= 1 ;i;i++ ){ 19 for ( int j= 1 ;j;j++ ){ 20 upMax(f[i][j],max(f[i- 1 ][j],f...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,467
精华内容 2,186
关键字:

动态规划算法数塔问题