首页 | 新闻 | 交流 | 问吧 | 文档 | 手册 | 下载 | 博客

整数拆分

作者:  时间: 2011-03-31

memo = []
def number_divide(m):
    global memo;
    n = m+1
    memo.append([])
    for i in range(1, n):
        memo.append([])
        memo[i].append(0)
        for j in range(1, n):
            memo[i].append(0)
            memo[i][1] = 1
    for i in range(1,n):
        for j in range(1,n):
            if i > j:
                memo[i][j] = memo[i][j-1]+memo[i-j][j]
            elif i == j:
                memo[i][j] = memo[i][j-1]+1
            else:
                memo[i][j] = memo[i][i]
    return memo[m][m-1]

while True:
    m = int( raw_input())
    print number_divide(m)

突然间看到有别人提到这个问题的。 知道算法,可是突然又想得不是特别明白,遂重新推了一下。

其实推不推一样。 理解问题,分析问题,表述问题。

1. 将一个整数n拆分为小于其本身的,且大于等于1的方法一共有几种呢?

也就是说,将n 拆分成各个单元都小于等于m (n-1)的方法一共有几种。

来看不同的case:

case1:  n==m, 假设已经知道了memo[n][n-1], 那么组成memo[n][n] = memo[n][n-1] + 1(只有一个n本身所组成)

case2: n <m: 这个时候利索当然的memo[n][n] = memo[n][n]。 因为n本身不可能用比n大的数表示

case2: n > m: 这个时候假设已经知道memo[n][m-1],那么我们可以知道接下来的memo[n][m],可以有两种表示方式,一种是包含了m这个数本身的。另外一个是没有包含m这个数字的。写成两部分得到:memo[n-m][m](一定包含了m这个数的)、memo[n][m-1](不包含m这个数的)两者相加就是memo[n][m]的方法了。

对于memo数组的叫法是: 把整数n拆分成小于等于m的数的不同拆分方法。

温故而知新。 处理问题时候的态度和方法也非常重要。

理解问题、分析问题、表述问题。