java - 将 n 写为两个或多个正整数之和的方法

Question

我在网上找到了一段关于计算将 n 写为两个或多个正整数之和的方法的代码。

我无法理解该功能是如何工作的。请有人给我解释一下

class sum
{
    static int countways(int n)
    {
        int table[]= new int[n+1];
        Arrays.fill(table,0);
        table[0]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                table[j]+=table[j-i];
            }
        }
        return table[n];
    }

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        countways[n];


    }
}

Answer 1

它计算将 n 写为两个或多个正整数之和的方法对于从 1 到 n 的所有整数。

想法是:

n = n0 + n1 + ... + nx = n0 + (n - n0)

我们迭代 n0 的可能值，并查看我们在此之前建立的表格，了解有多少种表达 (n - n0) 的方法。

这是 dynamic programming 更一般的想法的一个很好的例子。 。总体思路是，如果我们有一个递归问题，其中很多子问题都是相同的，我们可以通过保存子问题的结果并重用它们来节省时间。