一个经典的动态规划题目,一类动态规划的入门题目吧。地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1157
#include < stdio.h >

int table[105][105];

int dp[105][105];

int fun ( int f, int v )
{
    
    
int i, j, z;
    
    
for ( j = f; j<=v; j++ )
    
{
        dp[f][j] 
= table[f][j];
    }

    
    
for ( i=f-1; i>0; i-- )
    
{
        
for ( j = i; j<=v-f+i; j++  )
        
{
            dp[i][j] 
= -100000;
            
for ( z = j+1; z<=v-f+i+1; z++ )
            
{
                
if ( dp[i][j] < dp[i+1][z] + table[i][j] )
                
{
                    dp[i][j] 
= dp[i+1][z] + table[i][j];
                }

            }

        }

    }

    
    
int max = -100000;
    
for ( j = 1; j< v-f+1; j++ )
    
{
        
if ( max < dp[1][j] )
        
{
            max 
= dp[1][j];
        }

    }

    
    
return max;
    
}


int main ()
{
    
    
int f, v;
    
    
while ( scanf( "%d%d"&f, &v ) != EOF )
    
{
        
for ( int i=1; i<=f; i++ )
        
{
            
for ( int j=1; j<=v; j++ )
            
{
                scanf ( 
"%d"&table[i][j] );
            }

        }

        
        printf ( 
"%d\n", fun ( f, v ) );
    }

    
    
return 0;
}