精华内容
下载资源
问答
  • 数字三角形 动态规划

    千次阅读 2011-08-05 13:10:50
    /* 用opt[][]来记录已经产生的最优解 来解决对某些最优解进行重复求解的问题 */ #define LOCAL #include using namespace std; #define N 100 int a[N][N],opt[N][N]; int sum(int i
    /*
    用opt[][]来记录已经产生的最优解
    来解决对某些最优解进行重复求解的问题 
    */
    #define LOCAL
    #include<iostream>
    using namespace std;
    #define N 100
    int a[N][N],opt[N][N];
    int sum(int i,int j,int n)
    {
           if(opt[i][j])
                  return opt[i][j]+a[i][j];
           else
           {
    	       	  if(i==n-1)  return a[i][j];
                  if((opt[i][j]=sum(i+1,j,n))>(opt[i][j]=sum(i+1,j+1,n)))
                        return opt[i][j]+a[i][j];
    	   		  else 
                        return opt[i][j]+a[i][j]; 	
           }
    }
    int main()
    {
    #ifdef LOCAL
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
    #endif
        
        
        int i,j,n;
    	while(cin>>n)
    	{
    	       memset(opt,0,sizeof(opt));
    		   for(i=0;i<n;i++)
    		      for(j=0;j<=i;j++)
                     cin>>a[i][j];
    	       cout<<sum(0,0,n)<<endl;			 
        } 
        return 0;
    }
    

    展开全文
  • 动态规划 数字三角形

    2011-12-19 22:19:44
    数字三角形动态规划 使用C语言来实现 具体就是使用动态规划技术来编程
  • 数字三角形动态规划) 给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。 式第一行包含...

    数字三角形(动态规划)

    给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。

    在这里插入图片描述
    式第一行包含整数n,表示数字三角形的层数。接下来n行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。输出格式输出一个整数,表示最大的路径数字和。数据范围1≤n≤5001≤n≤500,
    −10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000输入样例:5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    输出样例:30

    动态规划的经典基础入门题,可是改bug改了好久,还是菜啊啊啊啊啊啊流泪。
    dp[i][j]代表走到第i行第j列的最大取值,根据题意dp[i][j]可以是由x=i-1,y=j-1或者x=i-1,y=j两个方向走过来的,因此我们选取max即可,这里的坑是每行的第一个数和第二个数只能由一个方向走过来,这里我们自己动手画画就可以了。

    废话不多说 上代码

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int map[105][105];
    int dp[105][105];
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                cin>>map[i][j];
                dp[i][j]=map[i][j];
            }
        }
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(j==1)dp[i][j]=dp[i-1][j]+map[i][j];
                else if(j==i)dp[i][j]=dp[i-1][j-1]+map[i][j];
                else
                {
                    dp[i][j]=dp[i-1][j-1]+map[i][j];
                    dp[i][j]=max(dp[i][j],dp[i-1][j]+map[i][j]);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,dp[n][i]);
        }
        cout<<ans;
    }
    
    展开全文
  • 动态规划数字三角形

    万次阅读 2018-03-28 11:24:23
    动态规划数字三角形 问题描述 问题: 给定一个由n行数字组成的数字三角形,如下图所示: 试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大(每一步只能从一个数走到下一层...

    动态规划之数字三角形

    问题描述

    问题:
    给定一个由n行数字组成的数字三角形,如下图所示:

    试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大(每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数)。

    输入格式:
      第一行是数字三角形的行数,接下来 n 行是数字三角形中的数字。
    输出格式:
      最大总和(整数)
    样例输入
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    样例输出
    30

    解法一:普通递归

    此解法的思想是从a[0][0]开始递归,len(a[i]][j]) = max(len(a[i+1][j]), len(a[i+1][j+1])) + a[i][j],递归到最底层之后开始对递归返回。
    对于n层的数字三角形,该解法的时间复杂度为2*(1+2+4+8+16+….+2^(n-1)),因而为O(2*2^n-1)约等于O(2^n)

    #include<iostream>
    #define MAX 101
    
    using namespace std;
    
    int a[MAX][MAX];
    
    int n;
    
    int max_sum(int i, int j)
    {
        int max1, max2;
        if(i == (n-1)) return a[i][j]; 
        max1 = max_sum(i+1, j);
        max2 = max_sum(i+1, j+1);
        if(max1>max2)
        {
            return max1+a[i][j];
    
        }
        else
        {
            return max2+a[i][j];    
        }
    }
    
    int main()
    {   
        int i = 0, j = 0;
        cin>>n;
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<=i; j++)
            {
                cin >> a[i][j];
            }
        }
    
        cout << max_sum(0, 0)<<endl;
    
        return 0;
    }
    

    解法二:记忆型递归

    此解法的思想是再开辟一块内存来代替递归时的记忆过程,时间开销基本不变,加上空间消耗,总体性能不如解法一。

    #include<iostream>
    #define MAX 101
    
    using namespace std;
    
    int a[MAX][MAX];
    int n;
    int maxnum[MAX][MAX];
    
    int max(int a, int b)
    {
        return a>b ? a : b;
    }
    
    int max_sum(int i, int j)
    {
        int max1, max2;
        if(i == (n-1)) 
        {
            maxnum[i][j] = a[i][j];
        }
        if(maxnum[i][j] != -1)
        {
            return maxnum[i][j];
        }
        max1 = max_sum(i+1, j);
        max2 = max_sum(i+1, j+1);
        maxnum[i][j] = max(max1, max2) + a[i][j];
    
        return maxnum[i][j];
    }
    
    int main()
    {   
        int i = 0, j = 0;
        cin>>n;
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<=i; j++)
            {
                cin >> a[i][j];
                maxnum[i][j] = -1;
            }
        }
        cout << max_sum(0, 0)<<endl;
        PrintArr();
        return 0;
    }
    

    解法三:递推型动规

    与解法二相比,这种解法以递推取代递归,避免了进栈出栈的时间开销。对于有n层的数字三角形,时间复杂度为O(n^2/2),约等于O(n^2)。

    #include<iostream>
    #define MAX 101
    
    using namespace std;
    
    int  a[MAX][MAX];
    int maxsum[MAX][MAX];
    int n;
    
    int max(int a, int b)
    {
        return (a>b ? a : b);
    }
    
    int max_sum(void)
    {
        int i = 0;
        int j = 0;
        int max1, max2;
        for(i = n-1; i>=0; i--)
        {
            for(j = 0; j<=i; j++)
            {
                if(i == (n-1))
                {
                    maxsum[i][j] = a[i][j];
                    continue;
                }
                max1 = maxsum[i+1][j];
                max2 = maxsum[i+1][j+1];
                maxsum[i][j] = max(max1, max2) + a[i][j];
    
            }
        }
        return maxsum[0][0];    
    }
    
    int main()
    {
        int i = 0, j = 0;
        cin>>n;
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<=i; j++)
            {
                cin >> a[i][j];
                maxsum[i][j] = -1;
            }
        }
    
        cout << max_sum()<<endl;
    
        return 0;
    }
    

    解法四:递推型动规空间优化

    解法四是对解法三的一种优化,在开辟辅助空间时不再开辟一个n*n的二维数组,而是采用长度为n的一维数组。因为对数字三角形的计算结果是自底向上的,对每一层的结果在上一层利用完之后就没用了,并且每一层的大小从低往上是递减的,因此可以开辟最下层大小的空间来保存每一层的计算结果。当然,时间复杂度仍为解法三的时间复杂度。

    #include<iostream>
    #define MAX 101
    
    using namespace std;
    
    int a[MAX][MAX];
    int maxsum[MAX];
    int n; 
    
    int max(int a, int b)
    {
        return (a>b ? a : b);
    }
    
    int max_sum(void)
    {
        int i = 0, j = 0;
        int max1, max2;
        for(i = n-1; i>=0; i--)
        {
            for(j = 0; j<=i; j++)
            {
                if(i == (n-1))
                {
                    maxsum[j] = a[i][j];
                    continue;
                }
                max1 = maxsum[j];
                max2 = maxsum[j+1];
                maxsum[j] = max(max1, max2) + a[i][j];
    
            }   
        }
        return maxsum[0];
    }
    
    int main(){
        int i = 0, j = 0;
        cin>>n;
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<=i; j++)
            {
                cin >> a[i][j];
                maxsum[i] = -1;
            }
        }
        cout << max_sum()<<endl;
    
        return 0;
    }

    解法五:递推型动规最终空间优化

    在完成解法四的时候我们发现:既然每一层的结果在用完之后该层就没用了,那么我们完全没有必要开辟额外的辅助空间–利用二维数组a本身最下层的空间就好了。

    #include<iostream>
    #define MAX 101
    
    using namespace std;
    
    int a[MAX][MAX];
    int n;
    
    int max(int a, int b)
    {
        return (a>b ? a : b);
    }
    
    int max_sum(void)
    {
        int i = 0, j = 0;
        int max1 = 0, max2 = 0;
        for(i = (n-2); i>=0; i--)
        {
            for(j = 0; j<=i; j++)
            {
                max1 = a[i+1][j];
                max2 = a[i+1][j+1];
                a[i][j] += max(max1, max2);
            }
        }
        return a[0][0];
    }
    
    int main()
    {
        int i = 0, j = 0;
        cin>>n;
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<=i; j++)
            {
                cin >> a[i][j];
            }
        }
        cout << max_sum()<<endl;
        return 0;
    }
    展开全文
  • 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];
        }
    }

     

    展开全文
  • 动态规划——数字三角形

    千次阅读 2018-10-09 15:28:03
    下图给出了一个数字三角形,请编写一个程序,计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。 (1)每一步可沿左斜线向下或右斜线向下 (2)1 &lt; 三角形行数 &lt; 100 (3)三角形数字为...
  • C++数字三角形问题(动态规划

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

    千次阅读 多人点赞 2020-03-18 16:21:30
     给定一个数字三角形,如上,在这个三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。求出这个最大和。 一. 我们先考虑使用递归来解决。 用二维数组D...
  • C++写的,利用动态规划解决数字三角形问题,含.cpp文件一个。
  • 数字三角形问题(动态规划

    千次阅读 2020-04-19 10:23:04
    数字三角形问题 1.题目描述:给定一个由n行数字组成的数字三角形,如图3-7所示。设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。算法设计:对于给定的由n行数字组成的数字三角形,...
  • 数字三角形问题 Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从...
  • C语言数字三角形动态规划

    千次阅读 2020-07-21 23:53:27
    图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 注意:路径上的每一步只能从一个数走到下一层上和它最近的左边...
  • 动态规划数字三角形

    千次阅读 2017-04-12 20:55:39
    问题: 给定一个由n行数字组成的数字三角形,如下图所示:  试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大(每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数)...
  •  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  径,使该路径所经过的数字的总和最大。  ●每一步可沿左斜线向下或右斜线向下走;  ●1三角形行数≤100;  ●三角形中的数字...
  • 1730-数字三角形问题(动态规划)java

    千次阅读 2019-03-17 21:11:36
    给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和...
  • B——数字三角形问题 ... // 动态规划法求: 数字三角形—1730 int main() { int n,i,j,D[101][101], a[101][101]; scanf("%d",&n); for (i=1; i<=n; i++) // 输入三角形 for(j=1; j<...
  • 给定一个由N行数字组成的数字三角形,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大,以及路径。
  • 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和...
  • @动态规划法 dp 题目描述 数字三角形 输入 数字三角形 输出 最佳路径 构思 1,递归写出暴力解法 2,用dp数组记忆重复元素 3,dp!=0,return dp 否则,记忆dp 代码展示 #include<stdio.h> int a[100][100]={0}...
  • 方法1:自底向上用“动态规划”选择 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优解 问题描述:...
  • 数字三角形问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条...
  • 动态规划-数字三角形

    2016-03-07 15:06:26
    动态规划:即保存递归的中间结果,减少递归次数 描述 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (图1) 图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到...
  • 数字三角形动态规划(C语言实现)

    千次阅读 2020-05-17 16:49:39
    (1)首先构造三个数组,第一个是存储三角形初始值的数组data[][];第二个是存储顶点到该点最大值的res[][]数组;第三个是存储该点上一个点的loc[][]数组。这里要对res[][]数组进行初始化-1; (2)按照三角形的层次...
  • 数字三角形问题Time Limit: 1000 ms Memory Limit: 65536 KiBSubmit StatisticProblem Description给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,719
精华内容 19,887
关键字:

数字三角形动态规划