【经典算法题】由整数拆分问题了解动规斜优

浅浅的花香味﹌ 2024-05-25 17:33 76阅读 0赞

## 前言 ##

**整数拆分问题是一个久远的数学问题，在数学上还没有明确的公式，但凭借者计算机强大的计算能力，可以得到解决整数拆分问题的公式，本文从整数拆分问题入手了解一种动态规划的经典优化策略:斜率优化。**

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

##  ##

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

## **一：整数拆分问题的历史** ##

**[从欧拉到拉马努金][Link 1]**  
上文中详细介绍了整数拆分问题的历史，至今从数学角度来说还未得到其准确计算的公式，但从计算机科学来说，通过计算机强大的算力可以容易的计算出其解。

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

## 二：问题的描述 ##

>     给定一个正数，将他表示成其它数字之和，且保证每一种放案都是递增的。请返回拆分整数的方法数。
>     例如正数1,裂开为[1]，方法数为1
>     例如正数2,裂开[1,1]和[2]方法数为2
>     例如正数3,裂开[1,1,1]和[1,2]和[3]三种方法

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

## 三：暴力递归解法 ##

### 1：思路 ###

> **?：我们可以通过这样一种策略来解决这个问题。因为拆出来的每一个数都要大于等于前面拆分出来的数字，因此我们可以枚举当前可能拆出来的数字，其余数字调用递归函数来帮我们拆分。**

### 2：代码 ###

public static int splitNum(int num){
            if(num<=0){
                return 0;
            }
            return process(1,num);
        }
        //递归含义：pre代表上一个拆分出来的数字
        //rest:表示还剩余要拆的数字
        public static int process(int pre,int rest){
            //base case
            if(rest==0){
                return 1;
            }
            //rest>0
            if(pre>rest){
                return 0;
            }
            //枚举出拆当前数字的可能性
            int ans=0;
            for(int n=pre;n<=rest;n++){
                ans+=process(n,rest-n);
            }
            return ans;
        }

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

## 四：记忆化搜索解法 ##

**?：存在大量重复解暴力递归一般都可以改成记忆化搜索。**

**?：暴力递归之所以暴力是因为其存在大量的重复解，我们可以通过加缓存的方式，把每一个已经算过的解全记录下来，等下次再使用的时候就可以直接从缓存中拿值，通过这样的策略可以过滤掉重复解，大大降低暴力递归的时间复杂度。**

**只需加个缓存即可，下面直接看代码。**

public static int splitNum(int num){
            if(num<=0){
                return 0;
            }
            HashMap<String,Integer> dp=new HashMap<>();
            return process2(1,num,dp);
        }
        //改成记忆化搜索
        public static int process2(int pre, int rest, HashMap<String,Integer> dp){
            String cur=pre+"_"+rest;
            if(dp.containsKey(cur)){
                return dp.get(cur);
            }
            //base case
            if(rest==0){
                dp.put(cur,1);
                return 1;
            }
            //rest>0
            if(pre>rest){
                dp.put(cur,0);
                return 0;
            }
            //枚举出拆当前数字的可能性
            int ans=0;
            for(int n=pre;n<=rest;n++){
                ans+=process2(n,rest-n,dp);
            }
            dp.put(cur,ans);
            return ans;
        }

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

## 五：动态规划 ##

**?：暴力递归从本质上就是将大问题拆分成子问题的策略，其从本质上就是动态规划的状态转移方程，我们可以通过对暴力递归分析出状态转移方程。**

**其普遍位置的状态转移方程是：dp\[i\]\[j\]=dp\[i\]\[j-i\]+dp\[i+1\]\[j-i-1\]+dp\[i+2\]\[j-i-2\]+...dp\[i+k\]\[j-i-k\]..**

**其中k是整数，i+k<=num j-i-k>=0**

**图例：整数5的拆分问题 图中五角星位置依赖于所有对号位置**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16][]

**我们可以通过上面的状态转移方程写出动态规划代码。**

### **代码：** ###

public static int dpWays1(int num){
            if(num<=0){
                return 0;//无效参数
            }
            int[][] dp=new int[num+1][num+1];
            //填第一列
            for(int pre=1;pre<=num;pre++){
                dp[pre][0]=1;
            }
            //填普遍位置,由位置依赖关系可以得知，要从下向上，从左向右填dp表
            for(int pre=num;pre>=1;pre--){
                for(int rest=pre;rest<=num;rest++){
                    for(int n=pre;n<=rest;n++){
                        dp[pre][rest]+=dp[n][rest-n];
                    }
                }
            }
            return dp[1][num];
        }

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

## 六：动态规划斜率优化 ##

**?：斜率优化本人的看法是A问题依赖的子问题域是RA,B问题依赖的子问题域是RB，问题求解策略是B->A(即先求解B再求解A)，而同时RB属于RA(即RB是RA的一部分），再做决策B的时候已经求解过RB了，再求解问题A的时候就没必要再次计算RA中包含的RB了。**

**本人能力有限对斜优的理解拘泥于表层，如果像深入了解，可以参考下面一位大佬的博文。**

**[斜率优化 辰星凌][Link 2]**

[斜率优化 脱水星球][Link 3]

**进行斜率优化后我们可以得到这个状态转移方程:dp\[i\]\[j\]=dp\[i+1\]\[j\]+dp\[i\]\[j-i\];**

**原本每一个dp\[i\]\[j\]位置都依赖于其dp\[i\]\[j\]所领导的斜率45°斜线上的所有位置的和，而这个计算过程，与dp\[i+1\]\[j\]有着大量的重复过程。**

public static int dpWays2(int num){
            if(num<=0){
                return 0;
            }
            int[][] dp=new int[num+1][num+1];
            //填特殊位置
            for(int i=1;i<=num;i++){
                dp[i][0]=1;
            }
            for(int i=1;i<=num;i++){
                dp[i][i]=1;
            }
            for(int pre=num-1;pre>=0;pre--){
                for(int rest=pre+1;rest<=num;rest++){
                    dp[pre][rest]=dp[pre+1][rest]+dp[pre][rest-pre];
                }
            }
            return dp[1][num];
        }

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

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了**

**点赞? 收藏✨ 关注✌**

[Link 1]: https://www.sohu.com/a/149838768_99893619
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/12abe19975b04271b0a70826206103cb.png
[Link 2]: https://www.cnblogs.com/Xing-Ling/p/11210179.html
[Link 3]: https://blog.csdn.net/PomeCat/article/details/72832494