fork(2) download
copy 
  1. #include <iostream>
  2. //typedef unsigned long long int ull;
  3.  
  4. int main() {
  5.     auto f = [](int n, int i, const auto& la) -> int {
  6.     	auto go = [&la,n](int j, const auto& lago) -> int {
  7.     		return j>3 ? 0 : la(n-j,j,la) + lago(j+1,lago);};
  8.         return n<0 ? 0 : n==0 ? 1 : go(i,go);};
  9.  
  10.     int n=3000; std::cout<<"without memoization: "<<f(n, 1, f)<<'\n';
  11.  
  12.     int dp[20000][3];
  13.     auto f_dp = [&dp](int n, int i, const auto& la) -> int {
  14.     	auto go = [&la,n](int j, const auto& lago) -> int {
  15.     		return j>3 ? 0 : la(n-j,j,la) + lago(j+1,lago);};
  16.  
  17.         auto memo = [&]() mutable -> int {
  18.         	if (dp[n][i]==0) dp[n][i]=go(i,go); return dp[n][i];};
  19.  
  20.         return n<0 ? 0 : n==0 ? 1 : memo();};
  21.  
  22.     std::cout<<"with memoization = dp: "<<f_dp(n, 1, f_dp)<<'\n';
  23. }
Success #stdin #stdout 3.93s 3660KB
comments (?)
stdin
copy 
3000
stdout
copy 
without memoization: 751501
with memoization = dp: 751501
https://ideone.com/3pP2Ot
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!