一、算法介绍

原理

思想将大问题划分为小问题进行解决从而一步步获取最优解的处理算法。按顺序求解子阶段前面子问题的解为后面子问题的求解提供信息。

如果某一问题有很多重叠子问题使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来。

动态规划算法的基本思想是将待求解的问题分解成若干个相互联系的子问题先求解子问题然后从这些子问题的解得到原问题的解对于重复出现的子问题只在第一次遇到的时候对它进行求解并把答案保存起来让以后再次遇到时直接引用答案不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

适用的情况

1. 最优化原理如果问题的最优解所包含的子问题的解也是最优的称该问题具有最优子结构即满足最优化原理。
2. 没有后效性即某阶段状态一旦确定就不受这个状态以后决策的影响。也就是说某状态以后的过程不会影响以前的状态只与当前状态有关。
3. 有重叠子问题子问题之间是不独立的一个子问题在下一个近阶段可能被多次遇到。这条性质不是动态规划适用的必要条件但是具备这条性质那么动态规划相对于其他算法就具备一定的优势。

做题步骤

1. 确定dp数组dp table以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

二、算法实例

1. 把数字翻译成字符串

题目来源牛客网
$等级中等$
涉及方法动态规划

👉题目描述

有一种将字母编码成数字的方式${}^{\prime }{a}^{\prime }->1{,}^{\prime }b->2^{\prime },...{,}^{\prime }z->26^{\prime }$。

现在给一串数字返回有多少种可能的译码结果

数据范围字符串长度满足 $0<n\le 90$
进阶空间复杂度 '$O(n{)}^{\prime }$时间复杂度 '$O(n{)}^{\prime }$

示例1

输入"12"
返回值2
说明2种可能的译码结果”ab” 或”l”  

示例2

输入"31717126241541717"
返回值192
说明192种可能的译码结果  

👉代码编写

👉👉方法1

对于普通数组1-9译码方式只有一种但是对于11-1921-26译码方式有可选择的两种方案因此我们使用动态规划将两种方案累计。

1. 用辅助数组dp表示前i个数的译码方法有多少种。
2. 对于一个数我们可以直接译码它也可以将其与前面的1或者2组合起来译码如果直接译码则$dp[i]=dp[i-1]$如果组合译码则$dp[i]=dp[i-2]$。
3. 对于只有一种译码方式的选上种$dp[i-1]$即可对于满足两种译码方式1020不能则是$dp[i-1]+dp[i-2]$
4. 依次相加最后的$dp[length]$即为所求答案。

import java.util.*;


public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        if (nums.length() == 1 && nums.charAt(nums.length() - 1) == '0'){
            return 0;
        }
        if (nums.length() == 1){
            return nums.length();
        }
        if (nums.charAt(nums.length() - 1) == '0' && 
           nums.charAt(nums.length() - 2) != '1' && nums.charAt(nums.length() - 2) != '2') {
            return 0;
        }
        int dp[] = new int[nums.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= nums.length(); ++i) {
            if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) <= '9' && nums.charAt(i - 1) > '0')
                || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) <= '6' && nums.charAt(i - 1) > '0')) {
                    dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[nums.length()];
    }
}

👉👉方法2

👉 注意点

👉 可以提炼的知识

2. 兑换零钱(一)

题目来源牛客网
$等级中等$
涉及方法动态规划

👉题目描述

给定数组arrarr中所有的值都为正整数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个$aim$代表要找的钱数求组成$aim$的最少货币数。
如果无解请返回-1.

数据范围数组大小满足 $0\le n\le 10000$ 数组中每个数字都满足 $0<val\le 10000$$0\le aim\le 5000$

要求时间复杂度 $O(n\times aim)$ 空间复杂度 $O(aim)$。

示例1

输入[5,2,3],20
返回值4

示例2

输入[5,2,3],0
返回值0

示例3

输入[3,5],2
返回值-1

备注
$0\le n\le 10000$
$0\le aim\le 5000$

👉代码编写

1. 可以用$dp[i]$表示要凑出i元钱需要最小的货币数。
2. 一开始都设置为最大值$aim+1$因此货币最小1元即货币数不会超过$aim$.
3. 初始化$dp[0]=0$。
4. 后续遍历1元到aim元枚举每种面值的货币都可能组成的情况取每次的最小值即可转移方程为$dp[i]=min(dp[i],dp[i-arr[j]]+1)$.
5. 最后比较$dp[aim]$的值是否超过aim如果超过说明无解否则返回即可。

👉👉方法1

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        if (aim < 1) {
            return 0;
        }
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1);
        dp[0] = 0;
        for (int i = 1; i <= aim; ++i) {
            for (int j = 0; j < arr.length; ++j) {
                if (arr[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
                }
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }
}

👉 注意点

搞清楚这个最小值是为什么就明白这道题了。
首先要遍历$1-aim$元每种面值都要进行枚举如果面值没有超过要凑的钱数$arr[j]<=i$才可以对该值进行维护$dp[i]=Math.min(dp[i],dp[i-arr[j]]+1)$。

$dp[i-arr[j]]+1)$ 这个的意思是 获得缺少当前面值的张数再加上当前面值的张数 $1$ 最后得出的结果。

👉 可以提炼的知识

3. 最长上升子序列(一)

题目来源牛客网
$等级中等$
涉及方法动态规划

👉题目描述

给定一个长度为 n 的数组 arr求它的最长严格上升子序列的长度。
所谓子序列指一个数组删掉一些数也可以不删之后形成的新数组。例如 [1,5,3,7,3] 数组其子序列有[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的当且仅当该序列不存在两个下标 $i$ 和 $j$ 满足 $i<j$且 $ar{r}_i\ge ar{r}_j$ 。
数据范围 $0\le n\le 1000$
要求时间复杂度 $O(n^2)$ 空间复杂度 $O(n)$

示例1

输入[6,3,1,5,2,3,7]
返回值4
说明该数组最长上升子序列为 [1,2,3,7] 长度为4

👉代码编写

👉👉方法1

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        int len = arr.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < len; ++i) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] >= arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

👉 注意点

这道题就非常的有意思我刚开始也没有想明白后来看了下大佬的做法原谅我第一次。

第一层循环我们遍历数组的时候从第二个数开始遍历。
第二成循环倒序遍历从$i-1$开始 到 $0$结束每次都将判断序列以$i$结尾的元素向前查找比$arr[i]$小的元素得到它们的dp数组记录上升序列的个数 $+1$与$dp[i]$ 取最大值即为当前i索引位置 最大上升序列
max的值是当前得到的最大上升子序列与原来的值进行比较。得到我们的最后结果。

👉 可以提炼的知识

4. 连续子数组的最大和

题目来源牛客网
$等级简单$
涉及方法动态规划

👉题目描述

输入一个长度为n的整型数组array数组中的一个或连续多个整数组成一个子数组子数组最小长度为1。求所有子数组的和的最大值。
数据范围:$1<=n<=2\times 10^5$

$-100<=a[i]<=100$

要求:时间复杂度为 $O(n)$空间复杂度为 $O(n)$
进阶:时间复杂度为 $O(n)$空间复杂度为 $O(1)$

示例1

输入[1,-2,3,10,-4,7,2,-5]
返回值18
说明经分析可知输入数组的子数组[3,10,-4,7,2]可以求得最大和为18        

示例2

输入[2]
返回值2

示例3

输入[-10]
返回值-10

👉代码编写

👉👉方法1

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        int[] dp = new int[len];
        dp[0] = array[0];
        int max = array[0];
        for (int i = 1; i < len; ++i) {
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

时间复杂度O(n)空间复杂度O(n)

👉👉方法2

优化上一个动态规划

public int FindGreatestSumOfSubArray(int[] array) {
        int sum = 0;
        int max = array[0];
        for(int i = 0; i < array.length; i++){
            // 优化动态规划确定sum的最大值
            sum = Math.max(sum + array[i], array[i]);
            // 每次比较保存出现的最大值
            max = Math.max(max, sum);
        }
        return max;
}

最终我们的时间复杂度O(n)空间复杂度O(1)

这里我们也是用了动态规划但是我们的空间复杂度降低了。仅使用一个 $sum$ 和 $max$ 来进行保存值即可。

👉 注意点

转移方程$dp[i]=Math.max(dp[i-1]+array[i],array[i]);$ 这个是上一个值与当前值相加与当前值进行比较从而得到目前的最大值。
max的值获得是通过我们原来保存的值上面得到的当前值进行比较。最终得到我们需要的值。

👉 可以提炼的知识

5. 最长回文子串

题目来源牛客网
$等级中等$
涉及方法动态规划

👉题目描述

对于长度为n的一个字符串A仅包含数字大小写英文字母请设计一个高效算法计算其中最长回文子串的长度。

数据范围 $1\le n\le 1000$
要求空间复杂度$O(1)$时间复杂度 $O(n^2)$
进阶: 空间复杂度 $O(n)$时间复杂度 $O(n)$

示例1

输入"ababc"
返回值3
说明最长的回文子串为"aba"与"bab"长度都为3

示例2

输入"abbba"
返回值5

示例3

输入"b"
返回值1

👉代码编写

👉👉方法1

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        int len = A.length();
        if (len == 1) {
            return 1;
        }
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; ++i) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        for (int j = 1; j < len; ++j) {
            for (int i = 0; i < j; ++i) {
                if (A.charAt(j) == A.charAt(i)) {
                    if (j - i == 1) {
                        dp[j][i] = true;
                    }else {
                        dp[j][i] = dp[j - 1][i + 1];
                    }
                    if (dp[j][i]) {
                        maxLen = Math.max(j - i + 1, maxLen);
                    }
                }
            }
        }
        return maxLen;
    }
}

空间复杂度$O(n^2)$ 时间复杂度$O(n^2)$

👉 注意点

这道题也非常有趣我们也会经常见过后面我会将类似的也会弄上来让大家学习。

$dp[j][i]$的含义为: 从 $i-j$ 的子串是否为回文子串.

1. 初始化的dp数组含义为 从$i-i$ 的 位置的 dp 为true 也就是单个字符都可以是回文子串
2. 第一层循环代表的是右边界我们使用了dp数组的一半另一半我们是不使用的。
3. 第二层循环代表的是左边界$i$每次从0开始递增到$j-1$的位置依次和$j$进行比较如果两者的索引字符是相等的并且两个字符是挨着的直接设置为true即可如果不是挨着的我们就需要看前面是否是回文字符串转移方程为 $dp[j][i]=dp[j-1][i+1]$。
4. 最后我们会看如果$dp[j][i]$为true那么我们获得最大的长度也就是maxLen