Memoized Log Cutting

• Time : $O(n^2)$
• Space : $O(n)$

// Your new function as given to you by me, your boss.
int cut_log(const std::vector<int>& p, int n){
    // Some array to store calculated values
    std::vector<int> dp(n + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n - i; j++) {
            dp[j+i] = std::max(dp[j+i], dp[j] + p[i]);
        }
    }
    return dp[n];
}