从暴力递归到动态规划的转换（推荐）

青旅半醒 2022-06-09 13:21 226阅读 0赞

# `从暴力递归到动态规划` #

`给一串数字，返回其能否转换成IP地址形式（IP地址的正确形式）。`

`如110.125.10.5`

`int P(i,p)`

`假设0...i-1都已经转成合法的IP段了，组成的IP段数是p个。`

`则有：`

`递归版本:`

/**
     * Created by YangGang on 2017/9/6.
     */
    public class ConvertStringToIP {
    
        public static int convertNum1(String str){
            //IP地址包括的数字个数范围在4~12
            if(str==null||str.length()<4||str.length()>12){
                return 0;
            }
            char [] chars=str.toCharArray();
            return process(chars,0,0);
        }
    
        public static int process(char [] chars,int i,int parts){
            //终止条件，一个是遍历结束，另一个是划分大于4部分，而IP只有4部分排除
            if(i>chars.length||parts>4){
                return  0;
            }
            //终止条件：已经到了结尾，看看是否正好分成4部分，若正好分成4部分则成功，否则失败
            if(i==chars.length){
                return parts==4?1:0;
            }
            //如果把自己作为一个部分，合法的个数
            int res=process(chars,i+1,parts+1);
            //如果当前字符是0，只能够把当前自己作为一段，因为IP中不可能出现012这种情况
            if(chars[i]=='0'){
                return res;
            }
            //如果当前字符不是0，则有可能是当前字符和下一字符一起构成一个部分。
            res+=process(chars,i+2,parts+1);
            //当前字符不是0，和下两个字符一起构成一部分,注意IP一个段只能是0-255
            if(i+2<chars.length){
                int sum=(chars[i]-'0')*100+(chars[i+1]-'0')*10+(chars[i+2]-'0');
                if(sum<255)
                {
                    return res+process(chars,i+3,parts+1);
                }
                else {
                    return res;
                }
            }
            else {
                return res;
            }
        }
    }

递归：

第一步：了解BaseCase(不需要依赖任何，自己就知道自己的值)

第二步: 建立上下文关系

第三步：找好递归出口（边界条件）

递归改写：

首先看process(char \[\] chars,int i,int parts)函数

如果i和parts确定了，返回值就确定了。

所以可以建立一个二维表：(i,parts---唯一的返回值)

自然要关注parts的取值,parts的空间可以开成6个：0,1,2,3,4，>4(5) ;

i的取值\[0,n+2\]。

则二维表如下：

0 1 2 3 4 5

n-1

n+1

n+2

(0,0)可能依赖(1,1)、(2,1)、（3,1）

![1pg][]

先确定最右边的值，之后就从右边往左来。

然后从BaseCase转化，先填写好。

![1pg][1pg 1]

填写好后，再按照递归指示顺序把表剩余部分填写完毕。

从下往上，从右往左填写。

![1pg][1pg 2]

实际上并不需要都去填写。

![1pg][1pg 3]

看看哪些位置是不用算的，在for循环中控制一下，可以进一步减少计算。

改写成的DP代码如下：

public static int convertNum2(String str){
            if(str==null||str.length()<4||str.length()>12){
                return 0;
            }
            char [] chars=str.toCharArray();
            int size=chars.length;
            int [][]dp=new int [size+3][5];
            //初始值
            dp[size][4]=1;
            for(int parts=3;parts>=0;parts--){
                //因为IP每个段最多3位（i=Math.min(size-1,parts*3)）
                for(int i=Math.min(size-1,parts*3);i>=parts;i=Math.min(i-1,parts*3)){
                    dp[i][parts]=dp[i+1][parts+1];
                    if(chars[i]!=0){
                        dp[i][parts]+=dp[i+2][parts+1];
                        if(i+2<chars.length){
                            int sum=(chars[i]-'0')*100+(chars[i+1]-'0')*10+(chars[i+2]-'0');
                            if(sum<256){
                                dp[i][parts]+=dp[i+3][parts+1];
                            }
                        }
                    }
                }
            }
            return dp[0][0];
        } 
    
    
    
     
     
     
     
     
    
    
    先算第3列，再算第2列，然后算第1列，最后算第0列。
     
     
    
     
     刨除那些不需要算的， 
     
     
    
     
     
    
     
     
    
     
     
    
     
     
     因为p是有限的，所以可以蜕化为O(n) 
     
    
     
     所以把递归转换成动态规划的步骤是： 
     第一步：确定解空间 
     第二步：看看哪些事都不依赖的（BaseCase）设好值 
     第三步：看看哪个状态是所求的状态 
     最后一步：确定计算顺序 
     具体到dp的决策，把递归中的决策抄下来就行了。

[1pg]: /images/20220609/fb48cf0029c947d593db180c21f583fa.png
[1pg 1]: /images/20220609/8b2025d34ed64ab68a358bb00ec888b1.png
[1pg 2]: /images/20220609/dd0f2c1e7d2a4c8f8274b990c9004e66.png
[1pg 3]: /images/20220609/21f919683b36440d8a6210a410068069.png