动态规划算法

动态规划十大经典问题

  • 最长公共子序列
  • 背包问题
  • 矩阵链路乘法
  • 编辑距离
  • 硬币找零问题
  • 最大子段和
  • 最长递增序列
  • 0-1背包问题
  • 划分问题
  • 合并排序问题

最长公共子序列

main(String[] args){
        List<String> list1 = Lists.newArrayList("1","3","4","5","6","7","7","8");
        List<String> list2 = Lists.newArrayList("3","5","7","4","8","6","7","8","2");
        int[][] dpArr = new int[list1.size()][list2.size()];
        for(int i=0;i<list1.size();i++){
            for(int j=0;j<list2.size();j++){
                if(i== 0 || j==0){
                    if(list1.get(i).equals(list2.get(j))){
                        dpArr[i][j] = 1;
                    }else{
                        dpArr[i][j] = 0;
                    }
                }else{
                    if(list1.get(i).equals(list2.get(j))){
                        dpArr[i][j] = dpArr[i-1][j-1] + 1;
                    }else{
                        dpArr[i][j] = Math.max(dpArr[i-1][j], dpArr[i][j-1]);
                    }
                }

            }
        }
        System.out.println(dpArr[list1.size() - 1][list2.size() -1]);
        int i = 0,j=0;
        String targetStr = "";
        while (i< list1.size() && j<list2.size()){
            if(list1.get(i).equals(list2.get(j))){
                targetStr += list1.get(i);
                i++;
                j++;
            }else if(dpArr[i+1][j] > dpArr[i][j+1]){
                i++;
            }else {
                j++;
            }
        }
        System.out.println(targetStr);
}

背包问题

main(String[] args){
//0-1背包
        //总容量
        int totalCapacity = 70;
        //每个物品的容量
        int[] capacityArr = new int[]{71,69,1};
        //每个物品的价值
        int[] valueArr = new int[]{100,1,2};
        int[] dpArr = new int[totalCapacity + 1];
        for(int i= 0;i<capacityArr.length;i++){
            for(int j=totalCapacity;j>=capacityArr[i];j--){
                dpArr[j] = Math.max(dpArr[j], dpArr[j-capacityArr[i]] + valueArr[i]);
            }
        }
        System.out.println(dpArr[totalCapacity]);
}

main(String[] args){
//0-1背包
        int totalCapacity = 70;
        int itemCount = 3;
        int[] valueArr = new int[]{71,69, 1};
        int[] capacityArr = new int[]{100, 1, 2};
        int[][] dpArr = new int[itemCount + 1][totalCapacity+1];
        for(int i=1;i<=itemCount;i++){
            for(int j=1;j<=totalCapacity;j++){
                if(capacityArr[i-1] > j){
                    //放不进去的时候
                    dpArr[i][j] = dpArr[i-1][j];
                }else{
                    dpArr[i][j] = Math.max(dpArr[i-1][j], dpArr[i-1][j-capacityArr[i-1]] + valueArr[i-1]);
                }
            }
        }
        System.out.println(dpArr[itemCount][itemCount]);
}
//完全背包问题讲解
https://blog.csdn.net/siyu1993/article/details/52858940

矩阵链路乘法

编辑距离

编辑距离又称莱温斯坦距离，是衡量两个字符串之间的相似度的一种算法。具体来说就是计算一个字符串转换成另外一个字符串所需要的最少的操作次数。常见的操作包括插入、删除、替换。
给出两个单词word1和word2，返回将word1转换成word2所需要的最少操作次数。对一个单词可以进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
    我们可以使用dp[i][j]来标识将word1的前i个字符转换成word2的前j个字符所需要的最少操作。初始化边界条件，然后填充整个dp表。
    1、如果word1[i-1] 和 word2[j-1] 相等，那么不需要进行任何操作，dp[i][j] = dp[i-1][j-1]
    2、如果不相同
  • 可以选择删除word1的第i个字符，对应dp[i-1][j] + 1（删除操作）
  • 可以在word1的第i个位置插入word2的第j个字符，对应dp[i][j-1] + 1（插入操作）
  • 可以降word1的第i个位置替换为word2的第j个字符，对应dp[i-1][j-1] + 1 (替换操作)
main(String[] args){
        String word1 = "daiwega";
        String word2 = "daidslgwe";
        char[] word1CharArray = word1.toCharArray();
        char[] word2CharArray = word2.toCharArray();

        int[][] dpArr = new int[word1.length() + 1][word2.length() + 1];
        for(int i=0;i<=word1.length();i++){
            dpArr[i][0] = i;
        }
        for(int j=0;j<=word2.length();j++){
            dpArr[0][j] = j;
        }

        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1CharArray[i-1] == word2CharArray[j-1]){
                    dpArr[i][j]=dpArr[i-1][j-1];
                }else{
                    dpArr[i][j] = Math.min(Math.min(dpArr[i-1][j] + 1, dpArr[i][j-1] + 1), dpArr[i-1][j-1] + 1);
                }
            }
        }
        System.out.println(dpArr[word1.length()][word2.length()]);
    }
}

硬币找零问题

main(String[] args){
        //硬币面额
        int[] coins = new int[]{5,2,1};
        int amount = 12;
        //dpArr[i] 标识凑出i金额时所需要的最少硬币数量
        int[] dpArr = new int[amount + 1];
        //初始化dpArr的值为amount + 1， 标识无法凑出
        Arrays.fill(dpArr, amount + 1);
        dpArr[0] = 0;
        for(int i=1;i<=amount;i++){
            for(int coin : coins){
                if(i>=coin){
                    dpArr[i] = Math.min(dpArr[i], dpArr[i-coin] + 1);
                }
            }
        }
        System.out.println(dpArr[amount] > amount?-1:dpArr[amount]);
}

最大子段和

main(String[] args){
        int[] numArr = new int[]{2,3,6,-3,5,5,-9};
        //answerArr[i] 前i个数的最大子段和
        int[] answerArr = new int[numArr.length + 1];
        for(int i=1;i<=numArr.length;i++){
            if(numArr[i-1] > 0){
                answerArr[i] = Math.max(answerArr[i-1],answerArr[i -1] + numArr[i-1]);
            }else{
                if(answerArr[i -1] + numArr[i-1] > 0){
                    answerArr[i] = answerArr[i -1] + numArr[i-1];
                }else{
                    answerArr[i] = 0;
                }
            }
        }
        int max = 0;
        for(int i=0;i<answerArr.length;i++){
            if(max<answerArr[i]){
                max = answerArr[i];
            }
        }
        System.out.println(max);


        //优化节省空间
        int res = 0;
        int b = 0;
        for(int i=0;i<numArr.length;i++){
            b+=numArr[i];
            if(b<0){
                b=0;
            }else{
                if(b>res){
                    res = b;
                }
            }
        }

        System.out.println(res);
}

最长递增序列

main(String[] args){
        int[] numArr = new int[]{1,2,3,1,5,6,2,3,6,7,8,9,10,1};
//        int[] numArr = new int[]{1,4,3,4,2,3};
        //dpArr[i] 标识前i个数字的最长子序列长度
        int[] dpArr = new int[numArr.length + 1];
        dpArr[0] = 0;
        Arrays.fill(dpArr, 1);
        for(int i=1;i<=numArr.length;i++){
            for(int j=1;j<i;j++){
                if(numArr[i-1]>=numArr[j-1]){
                    dpArr[i] = Math.max(dpArr[i], dpArr[j] + 1);
                }
            }
        }
        int max = 0;
        for(int i=0;i<dpArr.length;i++){
            System.out.println(dpArr[i]);
            if(max < dpArr[i]){
                max = dpArr[i];
            }
        }
}

0-1背包问题

有n个物品和一个容量为c的背包。每件物品有重量和起对应的价值，分别用w[i]和v[i]标识，我们需要将物品放到背包中，总重量不超过c，使其放入背包中的物品的总价值最大。
0-1背包问题的特点，每件物品只有一件，可以选择放入和不放入
我们使用动态规划来解决此类问题
首先我们来定义dp[i][j]来表示前i个物品放入容量为j的背包中所能获得的最大价值。

状态转移：

  • 当j<s[i]时，当前物品的重量大于背包的容量，物品无法放入背包，此时dp[i][j]=dp[i-1][j]
  • 当j>=s[i]是，当前物品的重量小于等于背包的容量，物品可以选择放入和不放入
    1、如果放入当前物品，则最大价值为dp[i-1][j-s[i]] + v[i],标识前i-1个物品房屋容量为j-s[i]的背包中的最大值加上当前物品的价值
    2、如果不放入，则最大值为dp[i-1][j],表示前i-1个物品放入容量为j的背包中的最大价值。

初始状态

  • dp[0][j] = 0,表示没有物品可选的时候，背包容量为j的时候最大价值为0
  • dp[i][0] = 0,表示背包容量为0的时候，无论有多少物品可选，背包最大价值为0
    代码如下
public static void main(String[] args) {
        //背包容量
        int c = 10;
        //物品重量
        int[] w = {1,2,4,3,3,5};
        //物品价值
        int[] v = {1,2,5,3,3,6};
        //物品个数
        int n = w.length;

        int[][] dp = new int[n+1][c+1];
        for(int i=0;i<=n;i++){
            dp[i][0] = 0;
        }
        for(int i=0;i<=c;i++){
            dp[0][i] = 0;
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=c;j++){
                //w[i-1] 表示第i个物品的重量
                if(w[i-1]>j){
                    //说明背包放不下当前的物品
                    dp[i][j] = dp[i-1][j];
                }else{
                    //v[i-1] 表示第i个物品的价值
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i-1]] + v[i-1]);
                }
            }
        }
        System.out.println(dp[n][c]);
    }

接下来我们来考虑如何节省算法需要的空间，我们可以定义dp[j]来表示当前背包容量为j的时候，所能装入物品的最大值

  • 选择装入物品i的最大值 dp[j] = dp[j-w[i]] + v[i]
  • 不装入物品i的最大值 dp[j] = dp[j]
    最终的递推公式为,dp[j] = max(dp[j], dp[j-w[i]] + v[i])
    算法如下
public static void main(String[] args) {
        //背包容量
        int c = 10;
        //物品重量
        int[] w = {1,2,4,3,3,5};
        //物品价值
        int[] v = {1,2,5,3,3,6};
        //物品个数
        int n = w.length;

        int[] dp = new int[c + 1];
        for(int i=0;i<=c;i++){
            dp[i] = 0;
        }
        for(int i=0;i<n;i++){
            //背包容量的遍历一定要从大到小遍历，因为我们递推公式中需要用到dp[j-w[i]] 来推到dp[j]的值，如果是
            //从小到达遍历的话，相当于把上一行dp[j-w[i]]的值给改变了
            for(int j=c;j>=0;j--){
                if(j<v[i]){
                    //背包容量小于当前物品价值，容量是从大到小的，j只能是越来越小，所以这个地方直接break
                    break;
                }
                dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
            }
        }
        System.out.println(dp[c]);

    }

另外还可以用回溯法来解决0-1背包的问题，参见:https://blog.csdn.net/qq_38046510/article/details/80061767
如果没见物品有多个，就是说每件物品可以选择多次，每件物品的数量放入数组counts中，算法如下：

/**
     * 多重背包问题二维数组实现
     * @param weights 物品重量数组
     * @param values 物品价值数组
     * @param counts 物品数量限制数组
     * @param capacity 背包容量
     * @return 能获得的最大价值
     */
    public static int solve(int[] weights, int[] values, int[] counts, int capacity) {
        int n = weights.length;
        // dp[i][j]表示前i种物品放入容量为j的背包的最大价值
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                int weight = weights[i - 1];
                int value = values[i - 1];
                int count = counts[i - 1];
                
                // 初始化为不选第i种物品的情况
                dp[i][j] = dp[i - 1][j];
                
                // 尝试选择k个第i种物品（k从1到最大可能数量）
                int maxK = Math.min(count, j / weight);
                for (int k = 1; k <= maxK; k++) {
                    int currentValue = dp[i - 1][j - k * weight] + k * value;
                    if (currentValue > dp[i][j]) {
                        dp[i][j] = currentValue;
                    }
                }
            }
        }
        
        return dp[n][capacity];
    }

多重背包可以转化成0-背包问题，然后通过0-1背包进行求解
几个0-1背包的变化应用：https://blog.csdn.net/2302_79177254/article/details/147579447

划分问题

给定一个整数n，求n可以被分成若干个正整数之后的不同方式的总数，划分中的数需要满足非递增顺序
我们使用dp[j]来表示总和为j的方案书，通过迭代的方式更新dp[j]的值
初始化 dp[0] = 1,表示凑成总和为0的方案书为1
初始化之后，对于每个数i(从1到n)，一次更新f[j] = f[j] + f[j-i],表示可以通过将i加到总和为j-i的方案中得到总和为j的方案
代码如下

public static void main(String[] args) {
        //要拆分的整数
        int n = 5;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                //dp[j] 表示i-1时和为j的个数，dp[j-1] 表示i-1时和j-1的个数
                dp[j] = dp[j] + dp[j-i];
            }
        }
        System.out.println(dp[n]);
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容