【算法】动态规划最佳路径求解

旧城等待， 2022-08-26 01:30 190阅读 0赞

**动态规划题目如下：**

**7**

**3 8**

**8 1 8**

**2 7 4 4**

**4 5 2 6 5**

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。  
求出最佳路径。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。  
  
  
**输入数据**  
输入的第一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N 行给出数字三角形。数字三角形上的数的范围都在0 和100 之间。  
**输出要求**

输出最大的和。

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_SIZE 10
    
    int SumValue[MAX_SIZE][MAX_SIZE];
    int MaxValue(int a,int b);
    int MaxSum(int i,int j,int data[MAX_SIZE][MAX_SIZE],int row);
    
    int main()
    {
    	int i,j;
    	int row = 0;
    	int data[MAX_SIZE][MAX_SIZE];
    
    	scanf("%d",&row);
    	memset(data, 0, sizeof(data));
    	memset(SumValue, -1, sizeof(SumValue));
    
    	for (i = 0; i < row; i++)
    	{
    		for (j = 0; j <= i; j++)
    		{
    			data[i][j] = rand() % 50;
    		}
    	}
    
    	int res = MaxSum(0,0,data,row-1);
    	printf("%d\n",res);
    
    	return 0;
    }
    
    int MaxValue(int a,int b)
    {
    	return a > b ? a : b;
    }
    
    int MaxSum(int i,int j,int data[MAX_SIZE][MAX_SIZE],int row)
    {
    	if (i == row)
    		return data[i][j];
    	else
    	{
    		if ( -1 == SumValue[i+1][j])
    			SumValue[i+1][j] = MaxSum(i+1,j,data,row);
    
    		if (-1 == SumValue[i+1][j+1])
    			SumValue[i+1][j+1] = MaxSum(i+1,j+1,data,row);
    
    		return (MaxValue(SumValue[i+1][j],SumValue[i+1][j+1])+data[i][j]);
    	}
    }