精华内容
下载资源
问答
  • 数字三角形问题动态规划)
    千次阅读
    2020-03-28 21:19:07

    题目:

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

    输入格式:

        5      //表示三角形的行数    接下来输入三角形
    
        7
    
        3   8
    
        8   1   0
    
        2   7   4   4
    
        4   5   2   6   5

    要求输入最大和

    思路:

    用D[i][j]存储点(i,j),maxsum[i][j]存储点(i,j)到底边路径的最大和。由于点(i,j)只能向(i+1,j)和(i+1,j+1)走,理所当然的知道要选择到底边和最大的那个点走(是到底边和最大的点,而不是数大的点);最后一行的maxsum和D相等(不用走,就是自己本身),所以就有递推公式:

    if i == n(最后一行)
    maxsum[i][j] = D[i][j];
    else
    maxsum[i][j] = max(maxsum[i+1][j],maxsum[i+1][j+1]) +D[i][j]

    初始状态为底边数字,值为底边数字值。

    从最后一行往上计算,算完的值存在maxsum中.

    代码:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int D[20][20];
    int n;
    int maxsum[20][20];
    /*递归法
    int MaxSum(int i,int j)
    {
        //表示已经计算过这个值了,可以直接取 不用重复计算
        if( maxsum[i][j] != -1 )
    		return maxsum[i][j];
    		//最后一行
        if(i == n-1)
            maxsum[i][j] = D[n-1][j];
    
        else{
            maxsum[i][j] =max(MaxSum(i+1,j+1),MaxSum(i+1,j))+D[i][j];
        }
        return maxsum[i][j];
    }
    */
    
    int main()
    {
    
        cin >> n;
        for(int i = 0;i < n;i++)
            for(int j = 0;j <= i;j++)
                {cin >> D[i][j];
                maxsum[i][j] = -1; }
       //递推法,从下往上计算
        for(int j = 0;j < n;j++)
            maxsum[n-1][j] = D[n-1][j];
        for(int i = n-2;i>=0;i--)
            for(int j = 0;j <=i;j++)
                maxsum[i][j] = max(maxsum[i+1][j],maxsum[i+1][j+1])+D[i][j];
        cout << maxsum[0][0];
    
        return 0;
    }
    

    要点:

    递归法为从上往下计算;而动态规划(递推法)是从下往上计算,无重复,一次到顶。

    更多相关内容
  • 部编第12章 线段与角动态问题(尖子).docx
  • 部编第12章 线段与角动态问题(同步).docx
  • 动态规划-数字三角形问题

    万次阅读 多人点赞 2018-11-04 19:23:44
    如果熟悉回溯法,可能会立刻发现这是一个动态的决策问题:每次有两种选择-左下或右下。如果用回溯法求出所有可能的路线,就可以从中选出最优路线。但和往常一样,回溯法的效率太低;一个n层数字三角形的完整路线有 ...

    有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数.

        1

       3 2

     4 10 1

    4 3 2 20

    从第一行的数开始,每次可以往左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来,如何走才能使得这个和尽量大?

    输入:三角形的行数n,数字三角形的各个数(从上到下,从左到右)

    输出:最大的和。

    运行结果:

    如果熟悉回溯法,可能会立刻发现这是一个动态的决策问题:每次有两种选择-左下或右下。如果用回溯法求出所有可能的路线,就可以从中选出最优路线。但和往常一样,回溯法的效率太低;一个n层数字三角形的完整路线有2^{n-1}条,当n很大时回溯法的速度将让人无法忍受。

    为了得到高效的算法,需要用抽象的方法思考问题:把当前的位置(i,j)看成一个状态(还记得么?)然后定义状态(i,j)的指标函数d(i,j)为从格子(i,j)出发时能得到的最大和(包括格子(i,j)本身的值)。在这个状态定义下,原问题的解是d(1,1)

    下面看看不同状态之间是如何转移的。从格子(i,j)出发有两种决策。如果往左走,则走到(i+1,j)后需要求“从(i+1,j)”出发后能得到的最大和“这一问题,即d(i+1,j)。类似得,往右走之后需要求解d(i+1,j+1)。由于可以在这两个决策中自由选择,所以应选择d(i+1,j)和d(i+1,j+1)中较大的一个,换句话说,得到了所谓的状态转移方程:

    d(i,j) = a(i,j) + max{d(i+1,j),d(i+1,j+1)}

    如果往左走,那么最好情况等于(i,j)格子里的值a(i,j)与”从(i+1,j)出发的最大总和“之和,此时需注意这里的最大二字。如果连”从(i+1,j)出发走到底部“这部分的和都不是最大的,加上a(i,j)之后肯定也不是最大的。这个性质称为最优子结构,也可以描述成全局最优解包含局部最优解。不管怎样,状态和状态转移方程一起完整的描述了具体的算法。

    int a[100][100],n,d[100][100];

    第一种方法是递归计算(需注意边界处理)。

    int solve1(int i,int j)
    {
        /* 递归 (重复计算,效率低) O(2^n)
        把当前位置(i,j)看成一个状态 d[i][j]为从格子出发能得到的最大和 解为d[1][1]
        d(i,j)=a(i,j) +max {d(i+1,j),d(i+1,j+1)} */
        return a[i][j]+(i==n? 0 : max(solve1(i+1,j),solve1(i+1,j+1)));
    }

    这样做是正确的,但时间效率太低,其原因在于重复计算。在solve(1,1)对应的调用关系树中,solve(3,2)被计算了两次(一次是solve(2,1)需要的,一次是solve(2,2)需要的)。也许读者会认为重复算一两个数没有太大影响,但事实是:这样的重复不是单个结点,而是一颗子树。如果原来的三角形有n层,则调用关系树也会有n层,一共有2^{n}-1个结点。

    递推计算(需再次注意边界处理):

    int solve2()
    {
        /*递推 (逆序枚举) O(n^2)
        i是逆序枚举的,计算d[i][j]前 所需要的d[i+1][j]
        和d[i+1][j+1]一定计算出来了*/
        int i,j;
        for(j=1;j<=n;j++)
            d[n][j]=a[n][j];
        for(i=n-1;i>=1;i--)
            for(j=1;j<=i;j++)
               d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);
        return d[1][1];
    }

    程序的时间复杂度显然是O(n^{2}),但为什么可以这样计算呢?原因在于:i是逆序枚举的,因此在计算d[i][j]前,它所需要的d[i+1][j]和d[i+1][j+1]一定已经计算出来了。

    可以用递推法计算状态转移方程。递推的关键是边界和计算顺序。在多数情况下,递推法的时间复杂度是:状态总数 * 每个状态的决策个数 * 决策时间。如果不同状态的决策个数不同,需具体问题具体分析。

    记忆化搜索。程序分成两部分。首先用 memset(d,-1,sizeof(d)); 把d全部初始化为-1,然后编写递归函数。

    int solve3(int i,int j)
    {
        //记忆化搜索 O(n^2)
         //题目中所说的各个数都是非负的 因此如果计算过某个d[i][j] 则应该非负
        if(d[i][j]>=0) //已经计算过
            return d[i][j];
        return d[i][j]=a[i][j]+(i==n? 0 : max(solve1(i+1,j),solve1(i+1,j+1)));
    }

    上述程序仍然是递归的,但同时也把计算结果保存在数组d中。题目中所各个数都是非负的,因此如果已经计算过某个d[i][j],则它应是非负的。这样,只需把所有d初始化为-1,即可通过判断是否d[i][j]>=0得知它是否已经被计算过。

    最后,千万不要忘记把计算之后把它保存在d[i][j]中,根据c语言 赋值语句本身有返回值的规定,可以把保存d[i][j]的工作合并到函数的返回语句中。

    上述程序的方法称为记忆化,它虽然不像递推法那样显式地指明了计算顺序,然仍然可以保证每个结点只访问一次。

    由于i和j都在1-n之间,所有不相同的结点一共只有O(n^{2})个。无论以怎样的顺序访问,时间复杂度均为O(n^{2})。从2^{n}-n^{2}是一个巨大的优化,这正是利用了数字三角形具有大量重叠子问题的特点。

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

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

    一、问题描述

    问题描述:给字一个由n行数字组成的数字三角形(等腰三角形)。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。

    ★算法设计:对于给定的由n行数字组成的数字三角形,计算从三角形的项至底的路径经过的数字和的最大值。

    ★数据输入:由文件input.txt提供输入数据。文件的第1行是数字三角形的计数n,1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。

    ★结果输出:将计算结果输出到文件output.txt。文件第1行中的数是计算出的最大值。

    输入文件示例:input.txt

    5

    7

    3 8

    8 1 0

    2 7 4 4

    4 5 2 6 5

    输出文件示例:output.txt

    30

    二、问题分析

    (1).输入数据的储存和表示:

    先将数字三角形由一个等腰变形为一个直角三角形,便于我们使用矩阵来保存和表示。

    矩阵表示如下:

    0 0 0 0 0 0

    0 7 0 0 0 0

    0 3 8 0 0 0

    0 8 1 0 0 0

    0 2 7 4 4 0

    0 4 5 2 6 5

    相应输入部分的代码:

    for(int i=1;i<=n;i++){

      for(int j=1;j<=i;j++){

      cinfile>>NT[i][j];

      }

      for(int j=i+1;j<=n;j++){

        NT[i][j]=0;

      }

    }

     

    (2).解题思路

    基本思路--采用自顶向下的方法

    A.思路一:自顶向下依次遍历,在碰到分叉路的时候选择较大的数。(错误--局部最优并不等于整体最优)

    比如上述例题按这种方法得到的“最优解”:7+8+1+7+5=27

    而实际上的最优解:7+3+8+7+5=30

    B.思路二:自顶向下依次遍历,列举出所有路径的大小,最后再进行比较。(正确)

    保存数据:首先,我们需要一个矩阵储存当前路径的大小,这里我们使用NT(number triangle)保存原来的数字三角形,使用ST(sum triangle)保存当前路径的大小。由于每个路径数据再往下发展的时候都有两种可能,因此这个矩阵的大小为n*2(n-1),这里的话我直接使用了2n。

    算法设计:

    初始化,ST[i][0]=0;ST[0][j]=0;ST[1][1]=NT[1][1]

    自顶向下遍历

    当前路径的和=上一层路径的和+当前数据;

    r[1][1]=a[1][1];

    for(int i=2;i<=n;i++){

    int count=1;

    for(int j=1;j<=i-1;j++){

    r[i][count++]=r[i-1][j]+a[i][j];//每一个数据对应两条路径

    r[i][count++]=r[i-1][j]+a[i][j+1];

    }

    }

    遍历结束后,ST的数据存储情况

     

    比如10就是路径:7+3的和;

    15就是路径:7+8的和;

    等等

     

    回溯最优路径:

    由于我们在计算最优路径时,用ST保存了所有当前路径的大小。因此我们只需要用最后的最优路径的数值依次往回减就可以求出最优路径了。由于我们的回溯是自底向上,路径的数据顺序是倒着的。因此这里使用了栈来储存路径数据,利用其后进先出的特点回溯出最优路径。

    三、详细设计(从算法到程序)

    #include<iostream>
    #include<stack> 
    #include<fstream>
    #include<sstream>
    using namespace std;
    //计算数字三角形最大路径的值
    int Numtri(int n,int **a,int **r){
    	r[1][1]=a[1][1];
    	for(int i=2;i<=n;i++){
    		int count=1;
    		for(int j=1;j<=i-1;j++){
    			r[i][count++]=r[i-1][j]+a[i][j];
    			r[i][count++]=r[i-1][j]+a[i][j+1];
    		}
    	}
    }
    //回溯最优路径
    int Traceback(int n,int posi,int **r,ofstream &outfile){
    	stack<int>trace; //建立一个堆栈,利用其后进先出的特点来打印出路径
    	int j=posi/2+1,c=r[n][posi];
    	for(int i=n-1;i>=0;i--){//从最后一层开始往上回溯
    		trace.push(c-r[i][j]);
    		c=r[i][j];
    		if(j%2==0) j=j/2; 
    		else j=j/2+1;
    	}
    	while(!trace.empty()){
    		outfile<<trace.top()<<" ";
    		trace.pop();
    	}
    }
    
    int main(){
    	ifstream cinfile;
    	cinfile.open("input.txt",ios::in);
    	int n;
    	cinfile>>n;
    	int **NT=new int *[n+1]();
    	int **ST=new int *[n+1]();
    	for(int i=0;i<=n;i++)
    	{
    		NT[i]=new int[n+1];
    		ST[i]=new int[2*(n+1)];
    	}
    	for(int i=0;i<=n;i++){
    		NT[0][i]=0;
    		NT[i][0]=0;
    	}
    	for(int i=1;i<=n;i++){
    	  for(int j=1;j<=i;j++){
    	  	cinfile>>NT[i][j];
    	  }
    	  for(int j=i+1;j<=n;j++){
    	    NT[i][j]=0;
    	  }
        }
        for(int i=0;i<=n;i++)
           for(int j=0;j<=2*n;j++) ST[i][j]=0;    
        cinfile.close();
        
        ofstream outfile;
        outfile.open("output.txt",ios::out);
        Numtri(n,NT,ST);
    	int Max=ST[n][1],pos=1;
    	for(int i=2;i<=2*n;i++){
    		if(Max<ST[n][i]){
    			Max=ST[n][i];
    			pos=i;
    		}
    	}
    	outfile<<Max<<endl;
    	Traceback(n,pos,ST,outfile);
    	return 0;
    }
    /*
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    */	

    四、程序运行结果

     

     

    五、分析与总结

     

    在做动态规划这一类问题时一定要注意很多时候局部最优解并不等于整体最优解。

    展开全文
  • 浙江版2016高考数学二轮复习5.3空间中的动态问题专题能力训练
  • 动态规划解决数字三角形

    千次阅读 多人点赞 2020-03-18 16:21:30
    问题描述:  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 
      
      给定一个数字三角形,如上,在这个三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。求出这个最大和。


    一. 我们先考虑使用递归来解决。

    用二维数组D来存放数字三角形,问题转换如下:

    D(i,j):表示第 i 行第 j 列的数字。(i,j从0开始)
    Sum(i,j):表示从 D(i,j) 到底边的最优解,即:从 D(i,j) 到底边的各条路径中,数字之和最大的一个。
    问题:求 Sum(0,0)。即:第0行第0列到底边的路径的最大和。

    1. 当只有一行时,它的最大路径和就是它本身。
      即:Sum(i,j) =D(i,j)
    2. 其次,它的最大路径和就是它本身加上它下面左右两个元素的最大路径和的较大者。因为是使用二维数组来存数字,就是它本身加上他正下方和他右下方两个元素的最大路径和的较大者。
      即:Sum(i,j) =max{Sum(i+1,j),Sum(i+1,j+1)}+D(i,j)

    写出递归方程:

    S u m ( i , j ) = { D ( i , j ) , i==N-1(底行) m a x { S u m ( i + 1 , j ) , S u m ( i + 1 , j + 1 ) } + D ( i , j ) , 0<i,j<N Sum(i,j) = \begin{cases} D(i,j), & \text{i==N-1(底行)} \\ max\{Sum(i+1,j),Sum(i+1,j+1)\}+D(i,j), & \text{0<i,j<N} \end{cases} Sum(i,j)={D(i,j)max{Sum(i+1,j)Sum(i+1j+1)}+D(ij),i==N-1(底行)0<ij<N

    根据递归方程写出递归函数。

    #include<iostream>
    using namespace std;
    const int N = 100;
    int D[N][N];
    int max(int a, int b)
    {
    	int m = a > b ? a : b;
    	return m;
    }
    int fun_d(int i,int j,int n)
    {
    	if (i == n-1)
    		return D[i][j];
    	int Sum_L = fun_d(i + 1, j, n);
    	int Sum_R = fun_d(i + 1, j + 1, n);
    	return max(Sum_L, Sum_R)+D[i][j];
    
    }
    int main()
    {
    	int n, i, j;
    
    	cin >> n;//n行数
    	for (i = 0; i < n; i++)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			cin >> D[i][j];
    		}
    	}
    	int MaxSum = fun_d(0,0,n);
    	cout << MaxSum << endl;
    	return 0;
    }
    

    在这里插入图片描述


    然而并没有,一般情况下,递归的时间复杂度都比较高,我们来看一下这个递归的时间复杂度。
    在这里插入图片描述

    嗯?花里胡哨的什么东西?
      
      这个表中红色的数字就是递归过程中每个元素要进行的计算次数,what?没错,就是存在大量的重复计算,这就导致了算法的时间复杂度非常高。将每行红色的数字加起来,就是这个算法的时间复杂度,即: O ( 2 n ) O(2^n) O(2n)。what?指数级别的时间复杂度,那肯定爆炸。所以,我又默默打开了电脑,打算用头发换思路。

    在这里插入图片描述


    改进:
      如果每算出一个元素的最优解,就把它保存起来,下次需要的时候直接调用即可,就可避免重复多次的计算。我们创建一个二维数组 Sum[M][N] 来保存最优解。那这样的时间复杂度是多少呢?一共需要计算多少个数据,时间复杂度就是多少,假设有 n 行数字,那么数字总数就是 n(n+1)/2,即:时间复杂度是 O ( n 2 ) O(n^2) O(n2)

    二. 通讯录式的递归方式。

    也称为记忆型的递归程序。
      我们牺牲空间和头发换时间,用一个二维数字 Sum[M][N] 来存放每一个元素到底边的最大和。初始时,给他每个元素都初始为 -1 ,表示该元素还没有计算出来过最优解。
      在递归的时候,如果 Sum[i][j] != -1,就表示该元素已经计算出来过最优解,我们可以直接调用它。然后当它递归到最后一行元素时,它的最优解就是当前的元素值。否则就在它正下方和右下方的元素的最优解中取一个较大者再加上该值发放该位置。

    C++实现:

    #include<iostream>
    using namespace std;
    const int N = 100;
    int D[N][N];
    int Sum[N][N];//存放每一个数字到底边的最大和
    int max(int a, int b)
    {
    	int m = a > b ? a : b;
    	return m;
    }
    int fun_f(int i, int j, int n)
    {
    	if (Sum[i][j] != -1)
    		return Sum[i][j];
    	if (i == n - 1)
    		Sum[i][j] = D[i][j];
    	else 
    	{
    		int Sum_L = fun_f(i + 1, j, n);//下方
    		int Sum_R = fun_f(i + 1, j + 1, n);//右下方
    		Sum[i][j] = max(Sum_L, Sum_R) + D[i][j];
    	}
    	return Sum[i][j];
    
    }
    int main()
    {
    	int n, i, j;
    
    	cin >> n;//n行数
    	for (i = 0; i < n; i++)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			cin >> D[i][j];
    			Sum[i][j] = -1;//表示该元素还没有计算出来最优解
    		}
    	}
    	int MaxSum = fun_f(0, 0, n);
    	cout << MaxSum << endl;
    	return 0;
    }
    

    Java实现:

    package abcd;
    
    import java.util.Scanner;
    
    public class Example2_1{
        public static void main (String args[]){
            Scanner in = new Scanner(System.in);
            int[][] D = new int[100][100];
            int[][] Sum =new int[100][100];
            int n,i,j;
            n= in.nextInt();
            for (i = 0; i < n; i++)
            {
                for (j = 0; j <= i; j++)
                {
                    D[i][j]=in.nextInt();
                    Sum[i][j] = -1;//表示该元素还没有计算出来最优解
                }
            }
            int MaxSum = fun_f(D,Sum,0, 0, n);
            System.out.println(MaxSum);
    
        }
        public static int fun_f(int[][] D,int[][] Sum,int i,int j,int n)
        {
            if (Sum[i][j] != -1)
            {
                return Sum[i][j];
            }
            if (i == n - 1)
            {
                Sum[i][j] = D[i][j];
            }
            else
            {
                int Sum_L = fun_f(D,Sum,i + 1, j, n);//下方
                int Sum_R = fun_f(D,Sum,i + 1, j + 1, n);//右下方
                Sum[i][j] = max(Sum_L, Sum_R) + D[i][j];
            }
            return Sum[i][j];
        }
        public static int max(int a, int b)
        {
            int m = a > b ? a : b;
            return m;
        }
    }
    

    在这里插入图片描述

    这个图就是最终每个元素到底部的最大路径和。

    它的最后一行就是本来的元素,嗯?是不是可以不用递归,用我们的 由已知推未知大法 是不是可以解决呢?

    在这里插入图片描述


    三. 由已知推未知大法

    算法思想:
      由上面可以看出,存最优解的二维数组的最后一行就是原来数组的最后一行的值,而且一个元素都是可以由该元素的正下方元素和右下方元素推出来,刚好可以根据最后一层元素,层层递推,直到推迟第0行第0列的元素。
      首先,给Sum数组的最后一行初始化为原本数组的最后一行,即:Sum[n - 1][i] = D[n - 1][i];
      然后,使用双层循环来递推每一个元素。即:Sum[i][j] = max(Sum[i + 1][j], Sum[i + 1][j + 1]) + D[i][j];

    #include<iostream>
    using namespace std;
    const int N = 100;
    int D[N][N];
    int Sum[N][N];//存放每一个数字到底边的最大和
    int max(int a, int b)
    {
    	int m = a > b ? a : b;
    	return m;
    }
    int fun_f_2(int n)
    {
    	int i, j;
    	for (i = 0; i < n; i++)
    	{
    		Sum[n - 1][i] = D[n - 1][i];
    	}
    	for (i = n - 2; i >= 0; i--)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			Sum[i][j] = max(Sum[i + 1][j], Sum[i + 1][j + 1]) + D[i][j];
    		}
    	}
    	return Sum[0][0];
    }
    int main()
    {
    	int n, i, j;
    
    	cin >> n;//n行数
    	for (i = 0; i < n; i++)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			cin >> D[i][j];
    		}
    	}
    	int MaxSum = fun_f_2(n);
    	cout << MaxSum << endl;
    	return 0;
    }
    

    呃呃呃,这样的话,算法的时间复杂度同样是 O ( n 2 ) O(n^2) O(n2),我们写它还有什么意义,莫慌、莫慌,且往下看。
      
      这个算法中,我们使用了二维数组来记录已求出的结果,然后进行层层递推,得到最终的结果。但是,我们可以看到,这个二维数组的每一行在完成它的递推任务之后,它就没用了,so,我们是不是可以用一个一维数组来代替这个二维数组呢?


    四. 压缩空间

    在这里插入图片描述

    这个图中,比如说要计算 D[3][0] 元素的最优解,就是 4 和 5 的较大者加上 D[3][0] ,算完之后,这个 4 就没用了,我们可以直接将 D[3][0] 元素的最优解 7 直接存放在 4 的位置上,循环往复。只需要一个一维数组就够了,最终,这个一位数组的首元素,就是最终的结果。

    #include<iostream>
    using namespace std;
    const int N = 100;
    int D[N][N];
    int max(int a, int b)
    {
    	int m = a > b ? a : b;
    	return m;
    }
    int Sum_1[N];
    int fun3(int n)
    {
    	int i, j;
    	for (i = 0; i < n; i++)
    	{
    		Sum_1[i] = D[n - 1][i];
    	}
    	for (i = n - 2; i >= 0; i--)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			Sum_1[j] = max(Sum_1[j] , Sum_1[j + 1])+D[i][j];
    		}
    	}
    	return Sum_1[0];
    }
    int main()
    {
    	int n, i, j;
    
    	cin >> n;//n行数
    	for (i = 0; i < n; i++)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			cin >> D[i][j];
    		}
    	}
    	int MaxSum = fun3(n);
    	cout << MaxSum << endl;
    	return 0;
    }
    

    嗯?一维数组?那个存原始数据的不就是的二维数组吗,二维数组不就是多个一维数组构成的嘛,有个大胆的想法,嘿嘿嘿,是不是这个一维数组也可以不要,用存原始数据的二维数组的最后一行来代替这个一维数组。


    五. 极限压缩

    C++ 实现:

    #include<iostream>
    using namespace std;
    const int N = 100;
    int D[N][N];
    int max(int a, int b)
    {
    	int m = a > b ? a : b;
    	return m;
    }
    int fun3(int n)
    {
    	int i, j;
    	for (i = n - 2; i >= 0; i--)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			D[n-1][j] = max(D[n-1][j] , D[n-1][j + 1])+D[i][j];
    		}
    	}
    	return D[n-1][0];
    }
    int main()
    {
    	int n, i, j;
    
    	cin >> n;//n行数
    	for (i = 0; i < n; i++)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			cin >> D[i][j];
    		}
    	}
    	int MaxSum = fun3(n);
    	cout << MaxSum << endl;
    	return 0;
    }
    

    Java实现:

    package abcd;
    import java.util.Scanner;
    public class Example2_1{
        public static void main (String args[]){
            Scanner in = new Scanner(System.in);
            int[][] D = new int[100][100];
            int n,i,j;
            n= in.nextInt();
            for (i = 0; i < n; i++)
            {
                for (j = 0; j <= i; j++)
                {
                    D[i][j]=in.nextInt();
                }
            }
            int MaxSum = fun3(D,n);
            System.out.println(MaxSum);
    
        }
        public static int fun3(int[][] D,int n)
        {
            int i, j;
            for (i = n - 2; i >= 0; i--)
            {
                for (j = 0; j <= i; j++)
                {
                    D[n-1][j] = max(D[n-1][j] , D[n-1][j + 1])+D[i][j];
                }
            }
            return D[n-1][0];
        }
    
        public static int max(int a, int b)
        {
            int m = a > b ? a : b;
            return m;
        }
    }
    

    编程之美,真的让人着迷。这就是许多编程大师以“聪明绝顶”为代价也要追求的东西。

    展开全文
  • 为解决扫描镜摆实时动态非接触测量问题,基于激光检测技术和CCD探测技术,提出一种红外地球敏感器扫描镜摆激光动态测试方法,并研制了扫描镜摆角动态测试系统,其可实现扫描镜的摆动频率、零位、幅值、峰峰值平均...
  • 根据喷油泵构造机理及机械原理,开发了一种实用的油泵相位角动态测试系统,该系统用单片机做控制器,在线测量油泵的动态相位参数,用单片机的C语言设计监控相位的数学模型,以便为油泵调试人员提供量的依据。...
  • 动态规划之背包问题——01背包

    千次阅读 多人点赞 2021-11-24 15:56:06
    文章目录一、01背包问题二、二维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 确定递推公式3. dp数组初始化4. 确定遍历顺序5. 举例推导dp数组三、一维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 一...
  • 动态规划详解(数字三角形POJ1163)

    千次阅读 多人点赞 2018-01-26 11:17:21
    那可以写一个程序模拟这个过程, 二维数组最后一行的值已经知道了,一层层 往上推,把这个最左上的那个数字的元素求到就完了嘛, 这个过程可以用递推来实现而不需要写递归函数,那具体的程序当然也是很简单的。...
  • 动态规划的方法,从左上开始,计算到达每一个点的最大收益。 /** * 用动态规划方法计算: * 用一个数组result[i][j]保存每一个点i,j的最大收益 * num[i][j], i=j=0 * result[i][j]=result[i][j-1]+num...
  • 数字三角形之动态规划(C语言实现)

    千次阅读 2020-05-17 16:49:39
    实例以及代码 问题描述:编写一个程序,计算从顶部开始到底部某处的路径上传递的最大数字总和。路径上的每步只能沿对线向左下或者右下滑动。 //res是存储最大值的数组,loc中存储的前一个点 int res[10][10],loc...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相...
  • 一个机器人位于一个 m x n 网格的左上 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下(在下图中标记为“Finish”)。 现在考虑网格中有障碍物。那么从...
  • 数字三角形问题(数塔问题

    千次阅读 2017-10-27 19:48:47
    数字三角形问题(数塔问题) Description 下图给出了一个数字三角形,请编写一个程序,计算从顶至底的某处的一条路径,使该路径所经过的数字和最大 Input 有很多个测试案例,对于每一个测试案例, 通过...
  • 动态规划求解01背包问题

    千次阅读 2019-04-22 21:35:05
    动态规划和分治法有些相像,都是把一个问题分成了很多子问题来求解,但是不同的是动态规划会记忆之前解决的子问题的结果,避免了重复计算。判断一个问题是否能用动态规划求解,要看它是否能划分成合适的子问题,然后...
  • 动态规划表格法详细解析01背包问题

    千次阅读 2020-08-15 16:06:45
    3.8 0-1背包问题(Knapsack problem) 前言:麻烦转载注明出处哦。 3.8.1 问题描述 其中每种物品只有1件,存放哪些物品,才能使背包存放物品价值最高? 3.8.2 算法思路 假设背包空间只有1kg、2kg…5kg,假设可装物品...
  • 基于01背包问题动态规划算法

    千次阅读 2020-08-12 00:31:59
    } (提交仍TLE) 动态规划中的最优决策表 以该图为例 在下图的表格中,每一个格子都代表着一个子问题,我们最终的问题是求最右下的格子的值(认真想想为什么?),也就是i=4,j=10时的值。这里,如果可选物品数量i为...
  • 在面试中遇到的一个问题,蚂蚁从(m,n)的网格一角爬到对(不能往回爬),查了一些东西,自己写下自己的一些理解,望大神指点。 从网格的一角爬到对,有多少中爬法。 理解部分: 将其进行转换,...
  • 动态规划算法思想解决找零钱问题

    万次阅读 2017-10-16 14:20:54
     关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受起来更易理解点;他人的文章写的再好,毕竟是别人的,学习...
  • 由于微信小程序中无法实现动态修改伪类元素的样式值【可能是我不会,会的同学可以指点一下】,所以,那颗占百分比的黄色五星,我用的是底部一个灰色五星+覆盖一个黄色五星,都是用的绝对定位,最后黄色五星...
  • 算法分析 关于动态规划的最少硬币问题的代码,
  • 背包问题-动态规划java实现代码

    千次阅读 多人点赞 2020-12-16 21:05:24
    背包问题-动态规划 背包问题是如今面试流行的面试题之一,我们可用动态规划解题
  • 触发问题|??

    千次阅读 2021-04-22 19:24:31
    系统的自动调节原理如下: 1)当系统的速度指令电压增大时,由于实际... 回答者: WISE - 助理工程师  第8级 2009-09-11 08:13:10 以下网友赞了您的问题: 填写您的评论... 提问者对于答案的评价: 谢了 暂无评论
  • 动态规划-硬币问题

    千次阅读 2018-09-28 14:52:35
    动态规划的本质是将原问题分解为同性质的若干相同子结构,在求解最优值的过程中将子结构的最优值记录到一个表中以避免有时会有大量的重复计算。 例如硬币组合问题,若求凑够11元的最少硬币数,可以先从凑够0元、1元...
  • 差异点:与分治法不同的是,适合用动态规划法求解的问题经分解得到的子问题往往不是相互独立的。有些问题分解后的子问题往往是重复的,此时若用分支法则会重复计算耗费时间内存。 总结:为了达到避免重复计算,可以...
  • [算法]动态规划解决数塔问题

    千次阅读 2019-04-30 09:47:00
    // 左下元素>右下元素 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 ]...
  • 旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次...
  • 动态规划求最大字段和问题

    千次阅读 2018-10-05 18:05:21
    1、最大子段和问题  问题定义:对于给定序列a1,a2,a3……an,寻找它的某个连续子段,使得其和最大。如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。  (1)枚举法求解  枚举法思路如下:  以a[0]...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 134,804
精华内容 53,921
关键字:

动态角问题

友情链接: MSP430IIC.zip