精华内容
下载资源
问答
  • 数字三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或者右下走。只需要求出这个最大和即可,不必给出具体...

    数字三角形

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

    • 在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或者右下走。只需要求出这个最大和即可,不必给出具体路径。

    • 三角形行数大于1小于等于100,数字为0-99

    • 直接递归的话时间复杂度太大,这里面有很多重复计算的点,所以创建一个和三角形一样大的二维数组,每当计算过这个点时就把值赋给这个数组。

    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    #define MAX 101
    int D[MAX][MAX];//存放三角形的数组
    int n;
    int maxSum[MAX][MAX]; //dp数组,用来记录已经算过的数
    
    int MaxSum(int i, int j) {
    	if (maxSum[i][j] != -1)  //如果maxSum中的值被修改过,意味着这个点已经被计算过,直接返回值就行了
    		return maxSum[i][j];
    	if (i == n)maxSum[i][j] = D[i][j];//如果到了底层,就返回自身
    	else {
    		int x = MaxSum(i + 1, j);//这是选择左下方的点
    		int y = MaxSum(i + 1, j + 1);//右下方的点
    		maxSum[i][j] = max(x, y) + D[i][j];//选择两个点中较大的加上现在所在的点
    	}
    	return maxSum[i][j];//返回计算过后的点
    }
    
    
    int main() {
    	memset(maxSum, -1, sizeof(maxSum));
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= i; j++) 
    			cin >> D[i][j];
    	cout << MaxSum(1, 1) << endl;
    }
    
    • 下面是递推式
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n;
    int D[101][101];
    int res[101][101] = {0};
    int main() {
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= i; j++)
    			cin >> D[i][j];
    	for (int i = 1; i <= n; i++)//把最后一行赋给res
    		res[n][i] = D[n][i];
    	//递推式,每次从下面一行选取较大的数与现在的相加
    	//res[i][j] = D[i][j] + max(res[i+1][j],res[i+1][j+1]);
    	for (int i = n - 1; i >= 1; i--)
    		for (int j = 1; j <= i; j++) {  //j可以取到i,因为这是res是上一行了
    			res[i][j] = D[i][j] + max(res[i + 1][j], res[i + 1][j + 1]);
    		}
    	cout << res[1][1] << endl;
    }
    
    展开全文
  • 动态规划 c++ 数字三角形 今天带来一道动态规划题,适合刚接触算法的新手。话不多说,直接上题! Description Format Input 第一行一个整数N(<=1000),表示三角形总共有几行 第二至第N+1行,给出这个数字...

    动态规划 c++ 数字三角形


    今天带来一道动态规划题,适合刚接触算法的新手。话不多说,直接上题!


    • Description
      在这里插入图片描述

    • Format Input
      第一行一个整数N(<=1000),表示三角形总共有几行 第二至第N+1行,给出这个数字三角形
    • Format Output
      一个整数,表示一路上所有数的最大和,结果不会超过int64

    • Sample Input
      4
      1
      3 2
      4 10 1
      4 3 2 20
    • Sample Output
      24

    没学过dp的码友看完题是不是一脸懵?没关系,接下来我呈上自己的思路

    先看题目。我们做编程题的主要思路中,有一个很重要的思路,就是从小推到大。那在这题中使用:
    首先一层的情况不用讨论,相信有脑子的都会

    然后看两层,我们是从上往下走求和,那就有两种方法:向左~ 向右~ 然后取一个更大的。

    那么很明显,需要用一个数组存下从最高层走到这个点上的最大数字和。这里用f[i][j]表示从第一行第一列到第i行第j列的最大数字和。这样,动态规划的第一个要点:所求状态就明确了。


    然后接下来要求的是状态转移方程。f[i][j]可能是从左上f[i-1][j-1]来的,也可能是从右上f[i-1][j]来的,而我们要求的是最大答案,所以要用到一个max函数。

    {
    	f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])//这里a数组是输入
    }
    

    这样,状态转移方程也得到了


    最后还要确定的两点是f数组最开始要确定的数,还有答案是什么。

    那么第一点,f初始值很明显,f[1][1]=a[1][1](作者习惯从1开始),即顶点数字和最大值就是输入值

    f[1][1]=a[1][1];
    

    第二点,答案,是最后一行的每个和的最大值

    int ans=0;
    for(int i=1;i<=n;i++)
    {
    	ans=max(ans,f[n][i]);
    }
    

    最后,把前面代码串起来加个输入,最后的源代码就出来了:

    #include<bits/stdc++.h>
    using namespace std;
    int n,a[1000][1000],f[1000][1000];
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	f[1][1]=a[1][1];
    	for(int i=2;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
    		}
    	}
    	int ans=0;
    	for(int j=1;j<=n;j++)
    	{
    		ans=max(ans,f[n][j]);
    	}
    	cout<<ans;
    	return 0;
    }
    

    最后还是求一波点赞支持!!!作者敲键盘也很累的OK!!!一遍看不懂的多看几遍消化消化,实在还不动评论区告诉我!!!

    展开全文
  • C++ 数字三角形(动态规划)

    千次阅读 2019-01-25 10:29:08
    一、题目 有三种方法实现: 这里就求权值之和...动态规划 思路和自底向上、自顶向下一样,只不过开多一个数组opt存储计算过的到达a[i][j]的权值之和最大的数 二、思路: 方法1:自底向上 1.从最后一行出...

    一、题目

        

       有三种方法实现: 这里就求权值之和最大的,最小的类似就不分析了。

       1.自底向上  缺点:算法复杂,重复计算

       2.自顶向下  缺点:重复计算,浪费时间

       3.动态规划 思路和自底向上、自顶向下一样,只不过开多一个数组opt存储计算过的到达a[i][j]的权值之和最大的数

     

    二、思路:

         方法1:自底向上

         1.从最后一行出发,例如,最后一行的2:

            如何得到走到2的权值之和最大数?(用递归

                   那就要先得到走到左上角的数(7)的权值之和最大的数,正上方的数(4)的权值之和最大的数。

            再比较两者哪个大,大的一个加上最后一行的数2,就是走到2的权值之和最大的数;

            同样,如何得到走到7的权值之和最大的数?或者是走到4的权值之和的最大数

                  就要先得到7的左上角的数(8)的权值之和的最大数,和正上方的数(1)的权值之和的最大数,再

            比较这两个权值之和哪个大,大的加上7;

            ……

            一直递推到第一行的数a[0][0],返回a[0][0]的值,然后回归,求得到达2的权值之和的最大数;

         2.比较走到最后一行(4,5,2,6,5)的各个权值之和,取得权值之和最大的数,然后输出

        实现程序:

    //  数字三角形
    //  7
    //  3 8
    //  8 1 0
    //  2 7 4 4
    //  4 5 2 6 5
    //  找出从第一层到最后一层的一条路,使得经过的权值之和最小或者最大,
    //  每一步只能向下或向右下方走。
    //  第一种方法:自底向上的思路
    //       缺点:算法有点复杂
    //  思路:从下面一个数开始往上计算,取sum(i-1, j-1)和sum(i-1, j)的最大值(即前面的权值之和最大值),加上当前值
    
    #include <iostream>
    
    const int max = 100;
    int a[max][max];
    int sum(int i, int j);
    
    int main(int argc, const char * argv[]) {
        int m = 0;
        int i, j, t, n;
        
        std::cin >> n; // 行数
        for(i = 0; i < n; i++) // 输入数字三角形
            for(j = 0; j <= i; j++)
                std::cin >> a[i][j];
        for(j = n-1; j >= 0; j--) {
            t = sum(n-1, j); // 计算走到最后一行每个数的权值之和
            if(m < t)
                m = t;
        }
        std::cout << m << std::endl;
        return 0;
    }
    
    // 递归:求走到第i行和第j列的权值之和最大的数
    int sum(int i, int j) {
        int x, y;
        
        if(i < j)
            return 0;
        if(i == 0)
            return a[0][0];
        else {
            x = sum(i-1, j-1); // 求到达左上角的数的权值之和最大数
            y = sum(i-1, j); // 求到达正上方的数的权值之和最大数
            if(x > y)
                return x+a[i][j];
            else
                return y+a[i][j];
        }
    }

    测试结果:

    方法2:自顶向下 和自底向上的思路刚好相反

        1.从a[0][0]出发:

           递推:得到从最后一行到正下方a[1][0]的权值之和最大的数,和从最后一行到右下方a[1][1]的权值之和最大的数

           回归:究竟是最后一行到a[1][0]的权值之和大,还是最后一行到达a[1][1]的权值之和大

                     取权值之和较大的,然后加上a[0][0],就是所求的权值之和最大的数

           那如何求得最后一行到a[1][0]的权值之和最大的数?或者是到a[1][1]的

           同样,求最后一行到正下方的数a[2][0]的权值之和,然后求最后一行到右下方的数a[2][1]的权值之和;

           取较大的权值之和,加上a[1][0]

           …

           一直递推,直到最后一行,然后返回最后一行的数

          接着回归求得从最后一行到a[0][0]的权值之和最大的数

        

        2.实现程序:

    //  数字三角形
    //  7
    //  3 8
    //  8 1 0
    //  2 7 4 4
    //  4 5 2 6 5
    //  找出从第一层到最后一层的一条路,使得经过的权值之和最小或者最大,
    //  每一步只能向下或向右下方走。
    //  第二种方法:自顶向下的思路
    //  缺点:重复计算,浪费时间
    
    #include <iostream>
    
    const int max = 100;
    int a[max][max];
    int sum(int i, int j, int n); // 取得到达最后一行的权值之和最大的数
    
    int main(int argc, const char * argv[]) {
        int i, j, n;
        
        std::cin >> n; // 输入行数
        // 输入数字三角形
        for(i = 0; i < n; i++)
            for(j = 0; j <= i; j++)
                std::cin >> a[i][j];
        std::cout << sum(0, 0, n) << std::endl; // 调用函数
        return 0;
    }
    
    // 取得到达最后一行的权值之和最大的数
    int sum(int i, int j, int n) {
        int x, y;
        
        if(i == n-1) // 到最后一行,返回最后一行的数
            return a[i][j];
        else {
            x = sum(i+1, j, n); // 求得最后一行到a[i+1][j]的权值之和最大的数
            y = sum(i+1, j+1, n); // 求得最后一行到a[i+1][j+1]的权值之和最大的数
            if(x>y) // 取权值之和较大的加上a[i][j]
                return x+a[i][j];
            else
                return y+a[i][j];
        }
    }

    方法3动态规划

    1.思路:和自底向上和自顶向下思路一样,只不过,用多一个数组opt存储计算过的到达a[i][j]的权值之和最大的数

    2.实现方法1:自顶向下(结合动态规划)

    //  数字三角形
    //  7
    //  3 8
    //  8 1 0
    //  2 7 4 4
    //  4 5 2 6 5
    //  找出从第一层到最后一层的一条路,使得经过的权值之和最小或者最大,
    //  每一步只能向下或向右下方走。
    //  第三种方法:记忆化搜索,递归,自顶向下
    
    #include <iostream>
    
    const int MAX = 100;
    int a[MAX][MAX];
    int opt[MAX][MAX];
    int sum(int i, int j, int n); // 计算
    
    int main(int argc, const char * argv[]) {
        int i, j, n;
        
        std::cin >> n;
        memset(opt, 0, sizeof(opt)); // 清零
        // 输入数字三角形
        for(i = 0; i < n; i++)
            for(j = 0; j <= i; j++)
                std::cin >> a[i][j];
        std::cout << sum(0, 0, n) << std::endl; // 调用函数,求得最大的权值之和
        return 0;
    }
    
    // 递归:求最后一行到a[i][j]的权值之和最大的数
    int sum(int i, int j, int n) {
        if(opt[i][j] != 0) // 之前已经求过,直接返回
            return opt[i][j];
        if(i == n-1) { // 到达最后一行
            opt[i][j] = a[i][j];
            return a[i][j];
        } else {
            opt[i+1][j] = sum(i+1, j, n); // 求得最后一行到a[i+1][j]的权值之和最大的数
            opt[i+1][j+1] = sum(i+1, j+1, n); // 求得最后一行到a[i+1][j+1]的权值之和最大的数
            if(opt[i+1][j] > opt[i+1][j+1]) // 取权值之和较大的加上a[i][j]
                return opt[i+1][j] + a[i][j]; // 最后一行到a[i][j]的权值之和最大的数
            else
                return opt[i+1][j+1] + a[i][j];
        }
    }

    方法2:自底向上(结合动态规划)

    #include <iostream>
    
    const int max = 100;
    int a[max][max];
    int opt[max][max];
    void MaxSum(int n); // 求得数字三角形中从第一行到各个位置的权值之和最大的数
    
    int main(int argc, const char * argv[]) {
        int i, j, n, t;
        
        std::cin >> n; // 输入行数
        memset(opt, 0, sizeof(opt)); // 清零
        // 输入数字三角形
        for(i = 0; i < n; i++)
            for(j = 0; j <= i; j++)
                std::cin >> a[i][j];
        // 调用函数:求得数字三角形中从第一行到各个位置的权值之和最大的数
        MaxSum(n);
        t = 0;
        // 比较最后一行的权值之和,找到最大的一个输出
        for(i = 0; i < n; i++) {
            if(t < opt[n-1][i])
                t = opt[n-1][i];
        }
        std::cout << t << std::endl;
        return 0;
    }
    
    // 求得数字三角形中从第一行到各个位置的权值之和最大的数
    void MaxSum(int n) {
        int i, j;
        
        opt[0][0] = a[0][0];
        for(i = 1; i < n; i++) {
            // 计算每行第一个数的权值之和
            opt[i][0] = opt[i-1][0] + a[i][0];
            // 计算除开头和结尾之外的其他位置权值之和
            for(j = 1; j < i - 1; j++) {
                if(a[i][j]+opt[i-1][j] >= a[i][j]+opt[i-1][j-1])
                    opt[i][j] = a[i][j]+opt[i-1][j];
                else
                    opt[i][j] = a[i][j]+opt[i-1][j-1];
            }
            // 计算每行最后一个数的权值之和
            opt[i][i] = a[i][j]+opt[i-1][i-1];
        }
    }

     

    展开全文
  • DP里面少不了递归,当然也能混在搜索里面构成记忆化搜索作为优化,也可以用递推来动态规划。 具体你要我说动态规划是个什么东西,我也只能说说自己的理解: 满足条件: 最优子结构情况 (一个问题可以拆分成子问题...

    作为一个菜鸡,研究了几天的DP,把经典例题研究了几遍,现在,我在这发表一下自己的菜鸡见解,记录下我对DP的理解。


    DP里面少不了递归,当然也能混在搜索里面构成记忆化搜索作为优化,也可以用递推来动态规划。
    具体你要我说动态规划是个什么东西,我也只能说说自己的理解:

    满足条件:

    • 最优子结构情况 (一个问题可以拆分成子问题来解决。很多的DP都涉及到了01背包问题这种思想,比如对待这个状态的解决方法,他的下一个状态是,得到与抛弃两种情况的和,即为背包问题的拿与不拿)
    • 无后效性(即当前情况的结果对后面的结果没有影响,也就是说后面值的改变对当前情况没有任何影响)

    几种情况:(暂时就先这么写,日后等我见识了更多的dp种类,我再来改)

    • 记忆化递归————作为递归代码的一种优化,减少时间复杂度。
    • 记忆化搜索————在DFS这种极其暴力的情况下,爆栈的情况很容易发生,采用记忆化的情况来处理,也算是一种动态规划。
    • 分支递归————这个就是背包问题的概述,取或者不取的问题,一分二,二分四,2的n次方复杂度。这时候也是要记忆化来优化
    • 递推—————这种题目可以用滚动数组来做,做到不断的覆盖。

    综上,这个动态规划很重要的就是记忆化的操作。
    接下来是我学习DP的第一道入门题目


    在这里插入图片描述输入格式:
    5//三角形的行数。下面是三角形
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    输出最大和


    题目解析:
    假定maxsum(i,j)表示从i,j这个点到最后一行的最大和
    D(i,j)表示i行j列的数字大小
    先设初始值i与j都为0,表示从(0,0)这个点开始到最后一行的最大和。
    那么可以分解为(0,0)的下和右下两个点到底部的最大和,其中最大的一个数加上D(0,0)本身的数字
    能够得到:maxsum(i,j)=maxsum( maxsum(i-1,j) , maxsum(i-1,j-1) )+D(i,j)

    这样就能得到初步代码


    #include<iostream>
    using namespace std;
    #define MAX 101 
    int D[MAX][MAX];
    int n;
    int maxsum(int i,int j)
    {
    	if(i==n)
    	return D[i][j];
    	int x=maxsum(i+1,j);
    	int y=maxsum(i+1,j+1);
    	return max(x,y)+D[i][j];
    }
    int main()
    {
    	int i,j;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		for(j=1;j<=i;j++)
    		{
    			cin>>D[i][j];
    		}
    	}
    	cout<<maxsum(1,1)<<endl;
    } 
    

    上面这个代码对于n比较小的情况是可行的,但是,时间复杂度是2的n次方级别,因为其中递归调用涉及到了重复计算,比如下图的红色数字为计算次数。
    在这里插入图片描述

    那么怎样进行优化呢?

    因为是重复计算,所以我们只需要对于重复计算的情况保存下来,下次要用到这个重复计算的值的时候,直接调用就可以了。这样就会大大节省时间。优化时间复杂度。

    优化步骤:

    • 建立数组存放已经算出来的值,并且全部初始化。
    • 寻找递归终止条件

    以下是优化代码


    #include<iostream> 
    #include<algorithm>
    using namespace std;
    int D[105][105];
    int n;
    int maxarray[105][105]={0};
    int MAX;
    int dg(int x,int y)
    {
    	if(maxarray[x][y])return maxarray[x][y];//如果这种情况计算过,直接返回 
    	if(x==n)maxarray[x][y]=D[x][y];//如果当前行数就是最后一行,那么只需要把当前位置的数字赋值给最大的情况 
    	else 
    	{
    		int p=dg(x+1,y);
    		int q=dg(x+1,y+1);		
    		maxarray[x][y]= max(p,q)+D[x][y];
    	}
    	return maxarray[x][y];
    	
    }
    int main()
    {
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<=i;j++)
    		{
    			cin>>D[i][j];
    		}
    	}
    	cout<<dg(0,0);
    }
    
    展开全文
  • C++数字三角形问题(动态规划

    千次阅读 2018-06-25 10:46:24
    ★问题描述:给字一个由n行数字组成的数字三角形(等腰三角形)。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 ★算法设计:对于给定的由n行数字组成的数字三角形,计算从...
  • 数字三角形 动态规划

    2018-10-22 21:48:10
    用二维数组存放数组三角形; D(r, j):第r行第j个数字(r,jcing1开始算) MaxSum(r,j):从D(r, j)到底边的各条路径中,最佳路径的数字之和。 所以问题化成求MaxSum(1,1): D(r,j)出发,下一步只能走D(r+1...
  • #include&lt;iostream&gt; #include&lt;math.h&gt; #include&lt;time.h&gt; #include&lt;stdlib.h&gt; using namespace std; int max(int a,int b){  return (a&......
  • poj1163 数字三角形 本机可以运行,提交就runtime error #include using namespace std; int record[105][105]; int idxhelper(int k) { return k*(k-1)/2; } int dp(int N, int s[]) { for(int i=1;...
  • 数字三角形 c++

    2016-06-28 09:16:12
    数字三角形 c++
  • 利用动态规划思想求解数字三角形问题
  • 动态规划 数塔问题 即数字三角形 IOI94年题 C++ 带文件
  • 数字三角形 题目 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (图一) 图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径,使该路径经过的数字总和最大。 每一步只能由当前位置向下或向...
  • 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和...
  • 找出数字三角形从上至下直接相邻的数字的最大和,每一行只能选出一个数字。 题目分析 我们按照一个一个类似矩阵的形式输入我们的数据,为了防止开辟多余的空间,我们直接在原输入的半矩阵上进行操作。 这个问题最好...
  • 下图中给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。 注意:路径上的每...
  • 数字三角形-动态规划

    2020-04-28 19:32:00
    给定一个由n行数字组成的数字三角形,设计一个算法,计算出从三角形的顶至底的一条路径,使该路径所经过的数字总和最大。 示例 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 路径只能是左斜线向下或右斜线向下 这个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,919
精华内容 3,567
关键字:

数字三角形动态规划c++

c++ 订阅