动态规划dp专题

爱被打了一巴掌 2023-07-17 09:57 3阅读 0赞

### dp专题 ###

*  斐波那契数列
 *  01背包问题
 *  最长不重复子字符串的长度
 *  分割数组的最大值
 *  最长公共子序列
 *  最大子序和
 *  买卖股票的最佳时期
 *  单词拆分
 *  整数拆分
 *  丑数
 *  剪绳子
 *  参考链接

# 斐波那契数列 #

> **写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项**。斐波那契数列的定义如下：  
> F(0) = 0  
> F(1) = 1  
> F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

dp实现

public static int fib(int n) { 
            if (n==0) return 0;
            if (n==1) return 1;
           int dp[]=new int[n+1];
           dp[0]=0;
           dp[1]=1;
           for (int i=1;i<n;i++){ 
               dp[i+1]=dp[i]+dp[i-1];
           }
           return dp[n];
        }

递归实现

public static int fib(int n) { 
            if (n==0) return 0;
            else if (n==1) return 1;
            else return fib( n - 1 )+fib( n - 2 );
        }

# 01背包问题 #

public class AppTest { 
       int kanapback(int n,int c,int[] w,int[] p){ 
           int dp[][]=new int[n+1][c+1];//注意是 N + 1，因为需要一个初始状态dp[0][0]，表示前0个物品放进空间为0的背包的最大收益
           /** * //对二维数组F进行初始化 * for(int j = 0; j <= V; j++) { * F[0][j] = 0; * } */
           //求解F[0 .. N][0 .. V]，即for循环从下至上求解
           for (int i=1;i<=n;i++){ 
               for (int j=0;j<=c;j++){ 
                   //如果容量为j的背包放得下第i个物体
                   if (j>=w[i-1]){ 
                       /** * 比如A,B,C * dp[i-1][j]假如表示已选了A，B的状态， * dp[i-1][j-w[i-1]]+p[i-1]则表示状态回退，j-w[i-1]是回到了A，p[i-1]则表示选择C，即当前多了c可选项的情况下A,C这个新的状态 */
                       dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+p[i-1]);//这是状态递推
                   }
                  //容量为j的背包放不下第i个物体，只能选择不放第i个物体
                   else { 
                       dp[i][j] = dp[i - 1][j];
                   }
               }
           }
            return dp[n][c];
       }
        @Test
        public void run() { 
            int c = 10;   //背包容量c
            int n = 5;    //物体个数n
            int[] w = { 2, 2, 6, 5, 4};   //物重w
            int[] p = { 6, 3, 5, 4, 6};   //物价p
            System.out.println(kanapback(n, c, w, p));
        }
    }

关于分析：请看  
[dim-dp][]  
[更多解析][Link 1]

# 最长不重复子字符串的长度 #

> 输入: “abcabcbb”  
> 输出: 3  
> 解释: 无重复字符的最长子串是 “abc”，其长度为 3。

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            if (s == null || s.length() == 0) { 
                return 0;
            }
            int[] dp = new int[s.length()]; // dp[i]表示以下标为i的字符结尾不包含重复字符的最长子字符串长度
            dp[0] = 1;
            int maxdp = 1;// 记录最大的值
            for (int dpIndex = 1; dpIndex < dp.length; dpIndex++) {  // 遍历每个位置
                int startP = dpIndex - dp[dpIndex - 1]; //以上一个位置结尾的，不包含重复字符的最长子字符串的起始位置
                int i;
                for (i = dpIndex - 1; i >= startP; i--) { // 从前一个位置回溯，看当前字符是否包含在 以上一个位置结尾的不包含重复字符的最长子字符串中
                    if (s.charAt(dpIndex) == s.charAt(i)) { //如果包含
                        break;  //如果没有break，代码执行完if语句后i会执行-1操作，现在有了break，当执行完break，立刻结束for循环，i不会执行-1
                    }
                }
                dp[dpIndex] = dpIndex - i;//以当前位置结尾的不包含重复字符的最长子字符串长度
                if (dp[dpIndex] > maxdp) { 
                    maxdp = dp[dpIndex];
                }
            }
            return maxdp;
        }
    }

[参考-力扣-更多解法][-_-]  
[参考-博客-dp代码解释][-_-dp]

# 分割数组的最大值 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]

class Solution { 
        public int splitArray(int[] nums, int m) { 
            int n = nums.length;
            int[][] f = new int[n + 1][m + 1];
            int[] sub = new int[n + 1];
            for (int i = 0; i <= n; i++) { 
                for (int j = 0; j <= m; j++) { 
                    f[i][j] = Integer.MAX_VALUE;
                }
            }
            for (int i = 0; i < n; i++) { 
                sub[i + 1] = sub[i] + nums[i];y
            }
            f[0][0] = 0;
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= m; j++) { 
                    for (int k = 0; k < i; k++) { 
                    //所有子数组各自和的最大值中最小值
                    //Math.min(f[i][j], Math.max(f[k][j - 1]这两个是状态回退
                        f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));//这行代码是状态更新，实现了【{7} {2,5}】,【{7,2} {5}】数组切割后的两两比较
                        //System.out.println("i:"+i+" j:"+j+" k:"+k+" f[i][j]:"+f[i][j]);
                    }
                }
            }
            return f[n][m];        
        }
    }

以i=3，j=3为例，即\{7，2，5\}分两组求解

> i:3 j:1 k:0 f\[i\]\[j\]:14  
> i:3 j:1 k:1 f\[i\]\[j\]:14  
> i:3 j:1 k:2 f\[i\]\[j\]:14  
> i:3 j:2 k:0 f\[i\]\[j\]:2147483647  
> i:3 j:2 k:1 f\[i\]\[j\]:7  
> i:3 j:2 k:2 f\[i\]\[j\]:7

3个元素只分一组f(3,1)

> f(0,0)===== 0个元素0组7，2，5一组  
> f(1,0)= 1个元素0组（把7分成0组，初始状态方程时f(1,0)=Integer.Max）2，5一组  
> f(2,0)= 2个元素0组====7，2，5一组

3个元素如果分2组f(3,2)

> f(0,1)===== 0个元素1组7，2，5一组  
> f(1,0)= 1个元素1组（7）2，5一组  
> f(2,1)= 2个元素1组（7，2）====5一组

# 最长公共子序列 #

[算法解析][Link 2]

public class Main { 
        static void LCS(String x, String y) { 
            int m = x.length();
            int n = y.length();
            //创建二维数组，也就是填表的过程
            int[][] c = new int[m + 1][n + 1];
    
            //初始化二维数组
            for (int i = 0; i < m + 1; i++) { 
                c[i][0] = 0;
            }
            for (int i = 0; i < n + 1; i++) { 
                c[0][i] = 0;
            }
            /** * C[i][j]表示最长公共子序列的长度 * path[i][j]表示路径 */
    
            //实现公式逻辑
            int[][] path = new int[m + 1][n + 1];//记录通过哪个子问题解决的，也就是递推的路径
            for (int i = 1; i < m + 1; i++) { 
                for (int j = 1; j < n + 1; j++) { 
                    //优先执行左边的字符与右边的字符比较，相等，则在原有基础上，将最长公共子序列个数+1,路径标左上箭头path[i][j]=0
                    if (x.charAt(i - 1) == y.charAt(j - 1)) { 
                        c[i][j] = c[i - 1][j - 1] + 1;
                    }
                    //不满足才走2：左边最长公共子序列的长度和上边最长公共子序列的长度比较，上>=左，将上的最长公共子序列的状态个数赋给当前，路径标向上箭头path[i][j] = 1
                    else if (c[i - 1][j] >= c[i][j - 1]) { 
                        c[i][j] = c[i - 1][j];
                        path[i][j] = 1;
                    }
                    //还不满足才走：将左边最长公共子序内的长度赋给当前状态，路径标左键头path[i][j] = -1
                    else { 
                        c[i][j] = c[i][j - 1];
                        path[i][j] = -1;
                    }
                }
            }
            //x表示行，m表示左边字符串长度，n表示右边字符串长度
            //最后输出结果
            PrintLCS(path, x, m, n);
    
        }
    
        public static void PrintLCS(int[][] path, String x, int i, int j) { 
            if (i == 0 || j == 0) { 
                return;
            }
    
            if (path[i][j] == 0) { 
                PrintLCS(path, x, i - 1, j - 1);
                System.out.printf("%c", x.charAt(i - 1));
            } else if (path[i][j] == 1) { 
                PrintLCS(path, x, i - 1, j);
            } else { 
                PrintLCS(path, x, i, j - 1);
            }
        }
    
        public static void main(String[] args) { 
    
            LCS("BDCBD", "ABCDZ");
        }
    }

# 最大子序和 #

*  当前元素 current element
 *  当前元素位置的最大和 current max sum
 *  迄今为止的最大和 max sum sesn so far  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public static int maxSubArray(int[] nums) { 
            int n = nums.length, maxSum = nums[0];
            for(int i = 1; i < n; ++i) { 
                if (nums[i - 1] > 0) nums[i] += nums[i - 1];
                System.out.println("nums[i]: " +nums[i]);
                maxSum = Math.max(nums[i], maxSum);
                System.out.println(maxSum);
            }
            return maxSum;
        }
        
        public static void main(String[] args) { 
           int[] nums = { -2,1,-3,4,-1,2,1,-5,4};
            maxSubArray(nums);
            //{4,-1,2,1} 结果为6
        }
    }

# 买卖股票的最佳时期 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 2]

*  可以采用动态规划，将数组中两个数的最大差问题转化为差数组中最大连续子列和问题  
    因为a\[6\] - a\[3\] = a\[6\] - a\[5\] + a\[5\] - a\[4\] + a\[4\] - a\[3\]

public int maxProfit(int[] prices) { 
           if(prices.length<=1) return 0;
            int[] diff=new int[prices.length-1];
            for (int i=0;i<prices.length-1;i++){ 
                diff[i]=prices[i+1]-prices[i];
            }
            int[] dp=new int[diff.length];
            dp[0] = Math.max(0,diff[0]);
            int profit = dp[0];
            for (int i = 1; i < diff.length; ++i) { 
                dp[i] = Math.max(0, dp[i-1] + diff[i]);
                profit = Math.max(profit, dp[i]);
            }
            return profit;
        }

优化后的代码

class Solution { 
        public int maxProfit(int[] prices) { 
        int last = 0, profit = 0;
        for (int i = 0; i < prices.length - 1; ++i) { 
            last = Math.max(0, last + prices[i+1] - prices[i]);
            profit =Math.max(profit, last);
        }
        return profit;
      }
    }

# 单词拆分 #

[原文链接][Link 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][20200323143927211.png]

public class Solution { 
        public static List<String> wordBreak(String s, Set<String> wordDict) { 
            LinkedList<String>[] dp = new LinkedList[s.length() + 1];
            LinkedList<String> initial = new LinkedList<>();
            initial.add("");
            dp[0] = initial;
            //遍历s
            for (int i = 1; i <= s.length(); i++) { 
                LinkedList<String> list = new LinkedList<>();
                //j每次从0开始，并不断向i收缩
                for (int j = 0; j < i; j++) { 
                    if (dp[j].size() > 0 && wordDict.contains(s.substring(j, i))) { 
                        //这里的dp[j]是状态回退，和下文组合起来就是状态递推方程
                        for (String str : dp[j]) { 
                            //System.out.println("str: "+str+" j,i,s.substring(j, i),s:"+j+","+i+","+s.substring(j, i)+","+s);
                            list.add(str + (str.equals("") ? "" : " ") + s.substring(j, i));
                        }
                    }
                }
                //for (String sss:list) System.out.println("i:"+i+" list:"+sss);
                //这里是状态更新
                dp[i] = list;
            }
            return dp[s.length()];
        }
    
        public static void main(String[] args) { 
            Set<String> stringSet = new HashSet<>();
            stringSet.add("cat");
            stringSet.add("cats");
            stringSet.add("and");
            stringSet.add("sand");
            stringSet.add("dog");
            String s = "catsanddog";
    
            List<String> ss = wordBreak(s, stringSet);
            for (String a : ss) System.out.println(a);
        }
    }

# 整数拆分 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 4]

i, j , dp[j] * dp[i - j] , dp[j] * (i - j) , j * dp[i - j] , j * (i - j) , dp[i]
    4, 1,        2,               3,              2,             3,              0
    i, j , dp[j] * dp[i - j] , dp[j] * (i - j) , j * dp[i - j] , j * (i - j) , dp[i]
    4, 2,        1,               2,              2,             4,              3
    i, j , dp[j] * dp[i - j] , dp[j] * (i - j) , j * dp[i - j] , j * (i - j) , dp[i]
    4, 3,        2,               2,              3,             3,              4

public class Main { 
        /** * 以10为例 * j * (i - j) 表示 3*7, 4*6, 5*5 * dp[j] * dp[i - j] ==》 dp[1]*dp[9]， dp[1]*dp[9]， dp[1]*dp[9] * dp[j] * (i - j)===> dp[9]*1, dp[8]*2, dp[7]*3 * j * dp[i - j]===》 9*dp[1], 8*dp[2], 7*dp[3] */
    
        public static int integerBreak(int n) { 
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 1;
            //i从3到10
            for (int i = 3; i <= n; i++) { 
                //j每次从1开始，逐渐向i靠拢
                for (int j = 1; j < i; j++) { 
    // System.out.println("i, j , dp[j] * dp[i - j] , dp[j] * (i - j) , j * dp[i - j] , j * (i - j) , dp[i]");
    // String re=i+", "+j+", "+dp[j] * dp[i - j]+", "+dp[j] * (i - j)+", "+j * dp[i - j]+", "+j * (i - j)+", "+dp[i];
    // System.out.println(re);
                    int t = Math.max(
                            Math.max(dp[j] * dp[i - j],
                                    Math.max(
                                            dp[j] * (i - j), j * dp[i - j])),
                            j * (i - j)
                    );
                    //状态回退可回退多步
                    //改造数组（最佳虚拟条件），转换问题，构造dp
                    dp[i] = Math.max(dp[i], t);
                }
            }
            return dp[n];
        }
    
        public static void main(String[] args) { 
            System.out.println(integerBreak(10));
        }
    }

# 丑数 #

求n个丑数

> 数据结构：int p2=0,p3=0,p5=0,minNum=1;list 数组存储状态。然后依次更新他们的值  
> 算法：动态规划

import java.util.ArrayList;
    import java.lang.Math;
    public class Solution { 
      public int GetUglyNumber_Solution(int index) { 
        if(index<=0){ 
          return 0;
        }
        if(index<7){ 
          return index;
        }
        int p2=0,p3=0,p5=0,minNum=1;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(minNum);
        while(list.size()<index){ 
          int m2 = list.get(p2)*2;
          int m3 = list.get(p3)*3;
          int m5 = list.get(p5)*5;
          minNum = Math.min(m2,Math.min(m3,m5));
          if(m2==minNum){ 
            p2++;
          }
          if(m3==minNum){ 
            p3++;
          }
          if(m5==minNum){ 
            p5++;
          }
          list.add(minNum);
        }
        return minNum;
        
      }
    }

# 剪绳子 #

> 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k\[0\],k\[1\],…,k\[m\]。请问k\[0\]xk\[1\]x…xk\[m\]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

> 解法分析：  
> 我们先定义函数f(n)为把绳子剪成若干段之后的各段长度乘积的最大值.在剪第一刀的时候,我们会有n-1种可能的选择,也就是说剪出来的第一段绳子的长度可能为1,2,…n-1.因此就有了递归公式 **f(n) = max(f(i)\*f(n-i))**,其中0<i<n.  
> 比如f(4)=max(f(2)\*f(2),f(1)\*f(3))

public class Solution { 
        public int cutRope(int n) { 
           // n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2,
            if(n==2)
                return 1;
            if(n==3)
                return 2;
            int[] dp = new int[n+1];
            /* 下面3行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3， 这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。 */
            dp[1]=1;
            dp[2]=2;
            dp[3]=3;
            int res=0;//记录最大的
            for (int i = 4; i <= n; i++) { 
                for (int j = 1; j <=i/2 ; j++) { 
                    res=Math.max(res,dp[j]*dp[i-j]);
                }
                dp[i]=res;
            }
            return dp[n];
        }
    }

# 参考链接 #

[dp解题思路][dp]  
[力扣-dp练习题][-dp]

[dim-dp]: https://blog.csdn.net/qq_41063141/article/details/90181994
[Link 1]: https://blog.csdn.net/u013885699/article/details/80248536?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
[-_-]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetcod/
[-_-dp]: https://blog.csdn.net/zxm1306192988/article/details/82079433
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]: /images/20230528/eb97418100824c619eb34b9442087d9a.png
[Link 2]: https://img-blog.csdnimg.cn/20190603072114736.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 1]: /images/20230528/a1b9636a536c43a3ae374cafbe389a48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 2]: /images/20230528/f2ce0491745a4d4f860889ae05cc9aa3.png
[Link 3]: https://leetcode-cn.com/problems/word-break-ii/solution/dan-ci-chai-fen-ii-by-leetcode/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 3]: /images/20230528/3bacaf3f7faf4bc190949cdf7d3ab291.png
[20200323143927211.png]: /images/20230528/2830a7399887487682bc66f27c3f7553.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 4]: /images/20230528/9b71c4c3d8a54f1f8cd090546daf7f1d.png
[dp]: https://www.cnblogs.com/huststl/p/8664608.html
[-dp]: https://leetcode-cn.com/problemset/all/