整数的划分（递归法, 打表搜索，动态规划法）

╰+哭是因爲堅強的太久メ 2022-03-14 10:48 244阅读 0赞

## 递归法： ##

直接举个例子什么是整数的划分。  
如有整数 **5**  
接下来对 **5** 经行划分

> 5 + 0  
> 4 + 1,  
> 3 + 2  
> 3 + 1 + 1,  
> 2 + 2 + 1  
> 2 + 1 + 1 + 1  
> 1 + 1 + 1 + 1 + 1

共 **7 种** 划分方法。

这里直接将用递归解决此问题的思路，  
通过看上面的对 5 的划分可以看出， 每种划分中必定有一个最大数（可以有多个）。  
我们可以将那个最大的数 成为 **m**， 而 **5** 是待划分的数， 称之为 **n**。  
接下来将数可以分为俩个部分， **m 和 n - m** （**n - m**就是除了最大的数其余的数的和了）。

**接下来对n ，m，和 n - m经行安排和分析。**

1.  当 **n == m** 时， 就是最大的数就等于 **n** 本身， 那么显然就只有一种划分方法就是 **n + 0**（除非你可以找出第二种，否则不要反驳）。
2.  当 **n < m** 时，就是最大的数大于了待划分的数， 那么显然时不存在的，因为不存在负数的划分（如果存在负数，那么也就不用存在这个问题了，答案必定时无穷种划分 ）。
3.  当 **n > m** 时， 这也是一般的情况，那么就将数分成两个部分\{m, 和 n - m\}，然后分别对两边经行划分，比如（如果此时划分成 **3 + 2** ，那么 **n - m = 2**， **m = 3**， 你可以发现 **2** 也是可以经行划分的， 那么也就不难理解为啥要n - m经行向下递推了 ）。
4.  当 **n == 1** 时， 那么就只有一种划分。
5.  当 **m == 1** 时， 也只有一种划分。

**结合以上情况经行分析：**  
当 **n == m** 时 因为出现了一种划分， 所以要 **+ 1**然后递推下去 **(n, m - 1)** ，  
当 **n < m** 时，那么最大的数应该是 **n** 所以是 **(n, n)** 。  
当 **n == 1** 或者 **m == 1**时， 就 **+ 1**， 并且结束，因为 **1** 不可以再经行划分了。  
当 **n > m** 时， 经行递推 **(n, m -1) + (n - m, m)**;

接下来将分析换算成代码。

int fun(int n, int m){ 
       if(n == 1 || m == 1){ 
       	return 1;
       }
       if(n == m){ 
       	return fun(n, m - 1) + 1;
       }
       if(n < m){ 
       // 这里其实应该时fun(n，n);
       // 但是n == m 时就会调用fun(n, m - 1); ，这里可以直接略过这部。
       	return fun(n , n - 1) + 1;
       }
       return fun(n, m - 1) + fun(n - m, m);
    }

--------------------

基于以上代码进行打表, 以增加搜索速度, 实际上就是动态规划了. 但写法还是舒服很多.  
速度不亚于动态规划的.

long num[10000][10000] = { 0};
    long fun(int n, int m){ 
    	if(n <= 0 || m <= 0) return 0;
    	if(n == 1 || m == 1) return 1;// 1种划分
    	
    	if(num[n][m]) return num[n][m]; 
    	
    	long ans = 0;
    	if(n <= m){ 
    		ans += fun(n, n - 1) + 1;
    	} else{ 
    		ans += fun(n, m - 1);
    		ans += fun(n - m, m);
    	}
    	
    	num[n][m] = ans;
    	return ans;
    }

--------------------

## 动态规划法: ##

思想和上面一样，动态规划主要是**记录了分化的结果**,极大的**减少划分次数**。  
一般要把**递归代码改写成动态**规划就要 **逆序** 的经行*迭代或者搜索*。  
那么如何记录结果呢？  
比如 **5 ，4**经行划分时就需要对**5， 3** 和 **1， 1**经行划分。  
如果在之前就对**5， 3**经行了划分呢？那么能不能记下来呢？  
对于整数的划分，当然是最大值越小越好划分，比如**5， 1** 就只有一种划分。

> 那么， 如果一开始就从 **5，1** 然后 **5， 2** 然后 **5，3** 这样经行划分，那么就可以省掉大部分的划分。  
> 由此提高效率。

java代码:

// 动态规划
    	static int dp(int n) { 
    		int result = 0;
    		int map[][] = new int[n + 1][n + 1];
    		int t = 0;
    		for(int i = 1; i <= n; i++) { 
    			for(int j = 1; j <= i; j++) { 
    				if(i == j) { // 比如 3, 3. 最大数为3是一种划分
    					// 3, 3 = 3, 2 + 1
    					map[i][j] = map[i][j - 1] + 1;
    				}else if(1 == j) { // 这里i == 1 可以省略
    					map[i][j] = 1;
    				} else { 
    					t = i - j;
    					// 如果i - j < j 那么就等同于i - j, i - j这种情况, 因为最大值不可能大于待分解值
    					if(t < j) { 
    						map[i][j] = map[i][j - 1] + map[t][t];
    					}else { 
    						map[i][j] = map[i][j - 1] + map[t][j];
    					}
    				}
    			}
    		}
    		result = map[n][n];
    		return result;
    	}