查找动态编程，特别是 Wikipedia 的页面和那里的斐波那契数列示例，并考虑如何在此处将其调整到您的问题中.

Possible Duplicate:
Generating the partitions of a number

Prime number sum

The number 7 can be expressed in 5 ways as a sum of primes:

• 2 + 2 + 3
• 2 + 3 + 2
• 2 + 5
• 3 + 2 + 2
• 5 + 2

Make a program that calculates, in how many ways number n can be expressed as a sum of primes. You can assume that n is a number between 0-100. Your program should print the answer in less than a second

Example 1:
Give number: 7 Result: 5

Example 2:
Give number: 20 Result: 732

Example 3:
Give number: 80 Result: 10343662267187

I've been at this problem for hours. I can't figure out how to get n from (n-1). Here are the sums from the first 30 numbers by a tree search

0 0 0 1 2 2 5 6 10 16 19 35 45 72 105 152 231 332 500 732 1081 1604 2351 3493 5136 7595 11212 16534 24441

I thought I had something with finding the biggest chain 7 = 5+2 and somehow using the knowledge that five can be written as 5, 3+2, 2+3, but somehow I need to account for the duplicate 2+3+2 replacement.

Look up dynamic programming, specifically Wikipedia's page and the examples there for the fibonacci sequence, and think about how you might be able to adapt that to your problem here.