我无法理解 o(sum) space 复杂度中硬币兑换问题的逻辑

Question

我在理解硬币找零问题的 O(sum) 复杂度解决方案时遇到困难。问题陈述是：给你一组硬币 A。假设你有无限数量的每枚硬币，你可以用多少种方式求和 B。

注意：

组 A 中的硬币将是唯一的。此问题的预期 space 复杂度为 O(B)。

解决方法是：

int count( int S[], int m, int n ) 
{ 
    int table[n+1]; 

    memset(table, 0, sizeof(table)); 

    table[0] = 1; 

    for(int i=0; i<m; i++) 
        for(int j=S[i]; j<=n; j++) 
            table[j] += table[j-S[i]]; 

    return table[n]; 
}

谁能给我解释一下这段代码？

Answer 1

首先，让我们确定函数中使用的参数和变量：

参数：

S包含所有m个硬币的面额。即每个元素包含每个硬币的价值。
m代表硬币面额的数量。本质上，它是数组 S 的长度。
n代表要达到的总和B。

变量：

table：数组 table 中的元素 i 包含给定硬币可以实现总和 i 的方法数。 table[0] = 1 因为只有一种方法可以实现总和为 0（不使用任何硬币）。
我遍历每个硬币。

逻辑：求和的方式数 j = 以下求和：

实现 j - S 总和的方法数[0]
实现总和 j - S[1] 的方法数 ...
总和j - S[m-1]的方法数（S[m-1]是第m个硬币的价值）

我没有完全破译或验证其余代码，但我希望这是朝着正确方向迈出的一步。

为代码添加了注释：

#include <stdio.h>
#include <string.h>

int count( int S[], int m, int n ) 
{ 
    int table[n+1]; 

    memset(table, 0, sizeof(table)); 

    table[0] = 1; 

    for(int i=0; i<m; i++) // Loop through all of the coins
        for(int j=S[i]; j<=n; j++) // Achieve sum j between the value of S[i] and n.
            table[j] += table[j-S[i]]; // Add to the number of ways to achieve sum j the number of ways to achieve sum j - S[i]

    return table[n]; 
}

int main() {
    int S[] = {1, 2};
    int m = 2;
    int n = 3;
    int c = count(S, m, n);
    printf("%d\n", c);  
}

备注：

代码避免重复：3 = 1+1+1、1+2（如果考虑 2+1，则使用 2 种方式而不是 3 种方式。
在价值方面不依赖于硬币的顺序。

我无法理解 o(sum) space 复杂度中硬币兑换问题的逻辑

I'm not able to understand logic of coin changing problem in o(sum) space complexity

dynamic-programming