Optimal Binary Search Tree

Problem
   Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

Solution
    dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j]) + sum[i->j];

Code
   

#include <stdio.h>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 260;
int n;
int a[N];
int sum[N];
int dp[N][N];
int main() {
    while (scanf("%d",&n) != EOF) {
        for (int i = 1;i <= n;i ++) {
            scanf("%d",&a[i]);
        }
        memset(dp,0x3f,sizeof(dp));
        sum[0] = 0;
        for (int i = 1;i <= n;i ++) {
            sum[i] = sum[i - 1] + a[i];
        }

        for (int i = 1;i <= n;i ++) {
            dp[i][i] = 0;
        }
        for (int len = 2;len <= n;len ++) {
            for (int i = 1;i + len - 1 <= n;i ++) {
                int j = i + len - 1;
                for (int k = i;k <= j;k ++) {
                    int tmp = 0;
                    tmp += sum[j] - sum[i - 1] - a[k];
                    tmp += k - 1 >= i ? dp[i][k - 1] : 0;
                    tmp += k + 1 <= j ? dp[k + 1][j] : 0;
                    dp[i][j] = min(dp[i][j],tmp);
                }
            }
        }
        cout << dp[1][n] << endl;

    }
    return 0;
}