Our great sponsors
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
} For C(n=5, k=2), the code above produces the following output: Top-down DP: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 3 3 -1 -1 -1 -1 -1 -1 4 6 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 C(n=5, k=2): 10 Bottom-up DP: 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 2 1 -1 -1 -1 -1 -1 1 3 3 -1 -1 -1 -1 -1 1 4 6 -1 -1 -1 -1 -1 1 5 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 C(n=5, k=2): 10 The time complexity is O(n * k) and the space complexity is O(n * k). In the case of top-down DP, solutions to sub-problems are stored (memoized) as needed, whereas in the bottom-up DP, the entire table is computed starting from the base case. Note: a small DP table size (V=8) was chosen for printing purposes, a much larger table size is recommended. Code All code is available at: https://github.com/vsmolyakov/cpp To compile C++ code you can run the following command: