数字三角形(动态规划)--算法学习-白红宇的个人博客

数字三角形(动态规划)--算法学习

发布日期：2021-05-15 00:27:53 浏览次数：14 分类：精选文章

本文共 3884 字，大约阅读时间需要 12 分钟。

��

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

��

��1��100�� 0 - 99

��

5 //��

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

��

��

�� //��

��

D( r, j) : ��r�� j ��(r,j��1��)

MaxSum(r, j) : ��D(r,j)��

�� MaxSum(1,1)

��

D(r, j)��D(r+1,j)��D(r+1, j+1)��N��

if ( r == N)

MaxSum(r,j) = D(r,j)

else

MaxSum( r, j) = Max{ MaxSum(r��1,j), MaxSum(r+1,j+1) } �� D(r,j)

��:

#include 
#include 
#define MAX 101 using namespace std;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; }

��

�� 2n,�� n = 100 ��

��

��MaxSum(r,j)��O(n2)�� n(n+1)/2

��

#include 
#include 
using namespace std;
#define MAX 101 int D[MAX][MAX]; int n;
int maxSum[MAX][MAX];
int MaxSum(int i, int j){
    if( maxSum[i][j] != -1 )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];
}
int main(){ int i,j; cin >> n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) { cin >> D[i][j];maxSum[i][j] = -1; }
cout << MaxSum(1,1) << endl; }

��

��

3 8

8 1 0

2 7 4 4

4 5 2 6 5

��4��2��2+4��2+��2+5��4��7.

��7+5��7+2��7+5��12��7��

��

��

#include
    
     
#include 
     
      
#include 
      
       
using namespace std;
#define MAX 101 int D[MAX][MAX]; int n;
int maxSum[MAX][MAX];
int MaxSum(int i, int j){
    if( maxSum[i][j] != -1 ) 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(){
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++) {
            cin >> D[i][j];
            maxSum[i][j] = -1;
        }
    cout << MaxSum(1,1) << endl;
}

��

��maxSum��MaxSum(r,j)��maxSum[100]��MaxSum��

��maxSum��D��n��maxSum��

��

#include
    
     
#include 
     
      
#include 
      
       
using namespace std;
#define MAX 101 int D[MAX][MAX]; int n;
int * maxSum;
int main(){
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++) {
            cin >> D[i][j];
        }
    maxSum = D[n]; // maxSum���������n���
    for( int i = n-1; i>=1; --i )
        for( int j=1; j<=i; ++j )
            maxSum[j] = max(maxSum[j], maxSum[j+1]) + D[i][j];
    cout << maxSum[1] << endl;
}

上一篇：动规解题的一般思路--算法学习

下一篇：求逆序数图解(分治)--算法学习

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章