动态规划设计
1. 最长子序列问题
最长上升不连续子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
// 最长上升不连续子序列，可以使用dp[j]，来表示前j个数的最长上升子序列，那么需要维护一个max来统计最大值
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int max = 1;
for(int i=1;i<nums.length;i++){
int curMax = 0;
for(int j=0;j<i;j++){
if(nums[i] > nums[j]){
curMax = Math.max(curMax,dp[j]);
}
}
dp[i] = curMax + 1;
max = Math.max(dp[i],max);
}
return max;
}// 当然更快速的方法是使用二分查找进行插入
递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7] 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
这里采用组合回溯的方法：
组合回溯模板主要用于生成非全排列的子集，同时可以用来尝试数值
组合回溯的模板
// 这里使用preIndex可以避免已经选过的，再次给当前位置赋值
// 每一次回溯实际是给当前位置curPos 进行赋值操作
public void backTrack(int[] nums,int curPos,int preIndex){
// 递归出口
if(curPos == k){
// 本题没有在这里return主要是由于，生成所有子集
return;
}
// 这里实际类似于给当前位置赋值
//backTrack(nums[curPos]=x1,curPos+1....)
//backTrack(nums[curPos]=x2,curPos+1....)
//backTrack(nums[curPos]=x3,curPos+1....)
for(int i=preIndex+1;i<nums.length;i++){
// 这里可以添加各种判断
// hashSet保证 当前位置不赋值相同的数，避免结果出现相同值，nums[curPos] = x;
backTrack(nums,curPos+1,i);
// 数组不需要回溯，直接赋值覆盖即可
}
} List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
// 枚举
if(nums == null || nums.length == 0){
return res;
}
backTrack(nums,new int[nums.length],0,-1,Integer.MIN_VALUE);
return res;
}
public void backTrack(int[] nums,int[] tmp,int curPos,int preIndex,int pre){
if(curPos >1){
List<Integer> list = new ArrayList<>();
for(int i=0;i<curPos;i++){
list.add(tmp[i]);
}
res.add(list);
}
HashSet<Integer> set = new HashSet<>();
for(int i=preIndex+1;i<nums.length;i++){
if(!set.contains(nums[i]) && pre <= nums[i]){
tmp[curPos] = nums[i];
set.add(nums[i]);
backTrack(nums,tmp,curPos+1,i,nums[i]);
}
}
}最长递增子序列的个数
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5
求最大长度的个数，实际是基于最大长度算法 进行更新
dp[i] 代表 dp[i] 以i结尾的子序列的最大长度，因为这里需要统计 最大长度的个数，思路是 某一个位置j num[j] < num[i] 的情况下， dp[j] > dp[i] , dp[i] 的 最大长度是dp[j] + 1, 那么他的最大个数是 count[i] += count[j] , 例如
1234 7 1235 7
// 思路，使用length 数组，记录，当前位置的最大长度，count[i] 统计当前位置最大长度的次数
public int findNumberOfLIS(int[] nums) {
if(nums == null || nums.length <= 1 ){
return nums.length;
}
int[] count = new int[nums.length];
int[] length = new int[nums.length];
Arrays.fill(count,1);
for(int i=1;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[i] > nums[j]){
if(length[j] >= length[i]){
length[i] = length[j] + 1;
count[i] = count[j];
}else if(length[j] + 1 == length[i]){
count[i] += count[j];
}
}
}
}
// 找到最长位置的index,返回最长位置数量
int maxLength = 0;
for(int i=0;i<nums.length;i++){
if(maxLength < length[i]){
maxLength = length[i];
}
}
int ans = 0;
for(int i=0;i<nums.length;i++){
if(maxLength == length[i]){
ans += count[i];
}
}
return ans;
}2.背包问题
背包问题就是选与不选的问题，问 容量w 和 物品 n 下选择最多价值，就先求1,1 ，12 ，等情况，反向递推
public int packet(int n, int k, int[] w,int[] v){
int[][] dp = new int[n+1][k+1];
for(int i=1;i<=n;i++){
for (int j=1;j<=k;j++){
if(j > w[i]){
dp[i][j] = Math.max(dp[i-1][j-w[i]] + v[i],dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][k];
}零钱兑换问题
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:
输入: coins = [2], amount = 3 输出: -1
public int coinChange(int[] coins, int amount) {
// 零钱兑换，就动态规划，找到兑换i的最少钱数
// dp[i] = min 遍历 dp[i-coins[j]] + 1
if(coins == null || coins.length == 0){
return -1;
}
int[] dp = new int[amount+1];
for(int i=1;i<=amount;i++){
// 这里最小的找钱次数是 amount + 1, 不要乱改
int min = amount+1;
for(int j=0;j<coins.length;j++){
if(coins[j]<=i)
min = Math.min(min,dp[i-coins[j]]+1);
}
dp[i] = min;
}
if (dp[amount] == amount+1){
return -1;
}
return dp[amount];
}零钱兑换问题2
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
零钱兑换问题2 是完全背包问题
暴力求解
public int change(int amount, int[] coins) {
// 零钱兑换问题
int[][] dp = new int[coins.length+1][amount+1];
dp[0][0] = 1;
for (int i=1;i<=coins.length;i++){
for (int j=0;j<=amount;j++){
for (int k=0;k*coins[i-1]<=j;k++){
dp[i][j] += dp[i-1][j-k*coins[i-1]];
}
}
}
return dp[coins.length][amount];
}再次进行优化， dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];
完全背包
public int change(int amount, int[] coins) {
// 零钱兑换问题
int[][] dp = new int[coins.length+1][amount+1];
for (int i=0;i<=coins.length;i++){
dp[i][0] = 1;
}
for (int i=1;i<=coins.length;i++){
for (int j=0;j<=amount;j++){
dp[i][j] = dp[i-1][j];
if(j > coins[i-1]){
dp[i][j] += dp[i][j-coins[i-1]];
}
}
}
return dp[coins.length][amount];
}将方法2中的dp[i][j] =dp[i - 1][j]+ dp[i][j - coins[i - 1]];dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]];去掉一维ii得到，dp[j]=dp[j+dp[j-coins[i]]]dp[j]=dp[j+dp[j−coins[i]]]这里ii从00开始的，不需要取coins[i-1]coins[i−1]
这里因为状态之和前一个状态相关可以取消
public int change3rd(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return dp[amount];
}分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
注意： 这里应该从后向前推导，防止数据重用，在只有前i个物品是 j为3 是减了一遍sum[i], j 为8 还要减一遍；
// 实际上可以转化为，子集中是否存在是二分之一的子集
// 采用枚举的方法进行dfs搜索
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0){
return false;
}
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum % 2 == 1){
return false;
}
// 子集分割实际为背包问题的变体
boolean[] dp = new boolean[sum/2+1];
dp[0] = true;
for(int i=0;i<nums.length;i++){
// 状态压缩后要注意遍历的顺序，这里每一个数字只能使用一次，所以应该从后往前推导
for(int j=sum/2;j>=1;j--){
if(j >= nums[i]){
dp[j] = dp[j] | dp[j-nums[i]];
}
}
}
return dp[sum/2];
}72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=0;i<=len1;i++){
dp[i][0] = i;
}
for(int i=0;i<=len2;i++){
dp[0][i] = i;
}
for(int i=1;i<len1+1;i++){
for(int j=1;j<len2+1;j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
}
}
}
return dp[len1][len2];
}高楼扔鸡蛋
若⼲层楼，若⼲个鸡蛋，让你算出最少的 尝试次数，找到鸡蛋恰好摔不碎的那层楼。
public int dp(int k, int n){
int res = n + 1;
for(int i=1;i<=n;i++){
res = min(res,max(dp(k-1,i-1),dp(k,n-i))+1);
}
}最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。
思路：当 s.char(i) == s1.char(j) 相等，dp[i][j] 与 dp[i-1][j-1] 状态有关
否则与 dp[i-1][j] 和 dp[i][j-1] 有关
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
int[][] dp = new int[len1+1][len2+1];
for (int i=1;i<=len1;i++){
for (int j=1;j<=len2;j++){
if (text1.charAt(i-1) == text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[len1][len2];
}最长回文子序列
给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为1000。
示例 1: 输入:
"bbbab" 输出:
4
思路： 如果两个字符相同，当前的大小是 dp[i+1][j-1] + 2;
否则， dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
public int longestPalindromeSubseq(String s) {
if(s.length() < 2){
return s.length();
}
int[][] dp = new int[s.length()][s.length()];
for (int i=0;i<s.length();i++){
dp[i][i] = 1;
}
for (int i=s.length()-2;i>=0;i--){
for (int j=i+1;j<s.length();j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}else{
dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
public boolean isMatch(String s, String p) {
int len1 = s.length();
int len2 = p.length();
if (len2 == 0){
return len1 == 0;
}
boolean first_match = len1 > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
if (p.length()>=2 && p.charAt(1) == '*'){
// 匹配0个 或者多个
return isMatch(s,p.substring(2)) || (first_match && isMatch(s.substring(1),p));
}
return first_match && isMatch(s.substring(1),p.substring(1));
} public boolean isMatch(String s, String p) {
char[] ss = s.toCharArray();
char[] pp = p.toCharArray();
boolean[][] dp = new boolean[ss.length+1][pp.length+1];
dp[0][0] = true;
for (int i=1;i<=pp.length;i++){
if (pp[i-1] == '*' && dp[0][i-2]){
dp[0][i] = true;
}
}
for (int i=1;i<=ss.length;i++){
for (int j=1;j<=pp.length;j++){
if (pp[j-1] == '*'){
if (pp[j-2] == ss[i-1] || pp[j-2] == '.'){
dp[i][j] = dp[i][j-1] || dp[i][j-2] || dp[i-1][j];
}else {
dp[i][j] = dp[i][j - 2];
}
}else {
if (ss[i-1] == pp[j-1] || pp[j-1] == '.'){
dp[i][j] = dp[i-1][j-1];
}
}
}
}
return dp[ss.length][pp.length];
}四键键盘
4 种， 就是题⽬中提到的四个按键，分别是 A 、 C-A 、 C-C 、 C-V （ Ctrl 简 写为 C ）。
// 按 num 下键盘， 可以产生多长的字符
public int maxA(int n, int num,int copy){
if (n <= 0) return num;
return Math.max(maxA(n-1,num+1,copy),
Math.max(maxA(n-1,num+copy,copy),maxA(n-2,num, num)));
}