How to Break Integers (StairCases) using Dynamic Programming?

Given an integer N, find out the number of method to sum up to N by integers given the following requirements:

1. Natural Numbers (Postive Integers) need to be strictly in ascending order (numbers cannot be duplicate).
2. There should be at least 2 numbers (natural numbers).

For example, given N=5, there are two ways to make 5 – which is 1 + 4 and 2 + 3. The 0 + 5, 1 + 2 + 2 do not satisfy the requirements.

This is actually the same problem but described differently in ACM/Timus/1017 Staircases

stair-cases

Solving using BFS

It might be possible to solve the problem using BFS (Breadth First Search) however the algorithm may take a while if the input N is large. We can start by building the BFS tree and the root node is 1 and we can expand the child nodes by putting numbers bigger than the parent node. When the sum equals to N, we increment the counter, and when the sum is greater than N, we simply stop expanding the tree.

Dynamic Programming

Given N, we know there exists always a solution which is N – but this is not allowed due to the requirement of “at least two numbers”. However, we can ignore this requirement and once we have the total number, we simply substract one from it.

One advantage of Dynamic Programming algorithm is that it can remember the intermediate results (sub problems). You could easily turn a recursion function that implements a recursive formula into DP by memorization.

Let F(n, k) be the number of ways making up to n with the maximum number k (which is also the last number in the equation). Therefore, we have

Where if we add 1 to the maximum number of F(n – 1, k – 1) and if we add K to the situation of F(n – k, k – 1). And the total number of the different solutions will be:

The C++ implementation of the above DP is as belows – which has O(N^2) both time and space complexity.

#include <iostream>
#include <vector>

typedef unsigned long long INT64;

int main()
{
	std::cin >> m;
	INT64 s = 0;
	std::vector <std::vector<INT64> > f(m + 1, std::vector<INT64>(m + 1, 0));
	f[1][1] = 1;
	for (int i = 2; i <= m; ++ i) // blocks
	{
		for (int j = 1; j <= i; ++ j) // max block
		{
			f[i][j] = f[i - 1][j - 1] + f[i - j][j - 1]; // DP equation
		}
	}
	for (int i = 1; i <= m; ++ i)
	{
		s += f[m][i];
	}
	std::cout << s - 1; // exclude the one-number solution
}

See also: Greedy Algorithm to Maximize the Split Product (Integer Break)

–EOF (The Ultimate Computing & Technology Blog) —