Time complexity: O(n * amount) — We fill a table of size n * amount, where n is the number of coins.
🧺 Space complexity: O(n * amount) — The DP table stores results for each coin and amount combination.
Code

[{"language":"C++","code":"class Solution {\npublic:\n\tint change(int amount, vector<int>& coins) {\n\t\tint n = coins.size();\n\t\tvector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));\n\t\tfor (int i = 0; i <= n; ++i) dp[i][0] = 1;\n\t\tfor (int i = 1; i <= n; ++i) {\n\t\t\tfor (int j = 1; j <= amount; ++j) {\n\t\t\t\tdp[i][j] = dp[i-1][j];\n\t\t\t\tif (j >= coins[i-1]) dp[i][j] += dp[i][j - coins[i-1]];\n\t\t\t}\n\t\t}\n\t\treturn dp[n][amount];\n\t}\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tint</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> change</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> amount</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> coins</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\t\tint</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> coins.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">size</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">();</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">\t\tvector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#2
Related Tags
