标签：return idx 16 int length str 动态 规划 dp

16. 动态规划

以下规则来自左程云老师的总结
1. 暴力递归的优化

有重复调用同一个子问题的解，这种递归可以优化

如果每一个子问题都是不同的解，无法优化也不用优化

2. 如何找到某个问题的动态规划方式

1）设计暴力递归：重要原则+4种常见尝试模型！重点！

2）分析有没有重复解：套路解决

3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决

4）看看能否继续优化：套路解决

3. 设计暴力递归过程的原则

1）每一个可变参数的类型，一定不要比int类型更加复杂

2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数

3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可

4）可变参数的个数，能少则少

4. 四个模型

1. 从左往右的尝试模型

2. 范围上的尝试模型：在[i,j]范围内xxx，特别在意讨论开头和结尾如何如何

   纸牌博弈

3. 多样本位置全对应的尝试模型：在范围[i,n]内xxx，特别在意讨论两个样本结尾如何如何

   最长公共子序列

4. 寻找业务限制的尝试模型：有某个回溯的参数，没办法估计范围。只能人为的给一个方法，确定上限

洗咖啡杯问题

注意动态规划for外面和里面的区分点：没有递归（return 数）的是边界条件，否则要在for里面

5. 套路

1）你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用

2）找到哪些参数的变化会影响返回值，对每一个列出变化范围

3）参数间的所有的组合数量，意味着表大小

4）记忆化搜索的方法就是傻缓存，非常容易得到

5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解

6）对于有枚举行为的决策过程，进一步优化

6. 动态规划的优化

1）空间压缩：将n * m的dp矩阵换成n * 1或者m * 1的（取决于mn谁小，尽可能的压缩空间）。

2）状态化简：一般来说，如果在dfs中出现了遍历的情况，可以考虑进行二次优化，看遍历能不能用某种公式替代，比如，dp[i] [j]可能是前3个数之和，那么dp[i] [j] = dp[i] [j-1] - dp[i] [j-1] 多的往前数第四个数 + 缺的那个数。类似于滑动窗口一样。

dp[i] [j] = dp[i] [j-1] - dp[i] [j-1-k] + nums[i] [j]

3）四边形不等式：以后

4）其他优化技巧：以后

16.1 机器人走路

1. 题目

机器人在一个长度为N（范围1-n）的地方，从start位置，走k步，到aim位置，有多少种方法。

2. 思路

直接动态规划，N个位置*K步的矩阵dp[n] [k]，其中，dp[start] [0] = 1，代表初始的时候，机器人在0的位置。

从第一列dp[1]开始遍历矩阵，如果dp[i-1] [j] 为1代表，dp[i] [j-1]和dp[i] [j+1]可以为累加dp[i-1] [j] 的值。

也就是说机器人已经走完了i-1位置，在决定 i 位置怎么走，有两种方式，上/下，也就是dp[i] [j-1]和dp[i] [j+1]

16.2 纸牌博弈

1. 题目

https://www.nowcoder.com/questionTerminal/7036f62c64ba4104a28deee98a6f53f6

​ 有一个整型数组A，代表数值不同的纸牌排成一条线。玩家a和玩家b依次拿走每张纸牌，规定玩家a先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家a和玩家b都绝顶聪明，他们总会采用最优策略。请返回最后获胜者的分数。

​ 给定纸牌序列A及序列的大小n，请返回最后分数较高者得分数(相同则返回任意一个分数)。保证A中的元素均小于等于1000。且A的大小小于等于300。

2. 思路

暴力递归：

​ 对于同一个情况[100,5,3]来说：

​ 先手视角：我先拿牌，拿完变成了后手，我要保证我选择的最大，我可以选择0，并且接受1-2的后手；也可以选择2，接受0-1的后手。毫无疑问，我要选最大的那个。

​ 后手视角：等先手拿完后，我就是先手了，此时的状态可能是0-1范围的先手，也可能是1-2范围的先手，而剩下的是哪个呢？最小的那个，因为先手会选走大的。

记忆化搜索（傻缓存）：

​ 傻缓存的主旨就是把return的值加入缓存中，如果遍历过了直接返回结果。这样防止再算一遍重复解。

动态规划：

​ 动态规划就是抽象出来问题，直接根据记忆化搜索加入dp的方式，直接生成dp。

​ 根据最原始的暴力递归得到f、g表的规律进而生成表。

1. 画一个表防止错乱。
2. 看base case得到最初的结果，并且写在表上
3. 看最初的调用得到真正我们需要的结果的位置，并且用※标记
4. 根据递归得到f、g表的各个位置的依赖方式，并且扩展到结果位置。

3. 代码

总:

	public static void main(String[] args) {
        int[] arr = {5,7,4,5,8,1,6,0,3,4,6,1,7};
        // 调用,在二者中选最大的
        int f = f(arr, 0, arr.length - 1);
        int g = g(arr, 0, arr.length - 1);
        System.out.println(Math.max(f,g));
    }

暴力递归：

    // 对于同一个情况来说的先手视角
    // 先手状态可以选牌，后手状态无法选牌，只能等待状态的改变。
    public static int f(int[] num, int l,int r){
        // 只剩下一张牌的情况
        if(l==r){
            return num[r];
        }

        // 我如果是先手的状态，我选择了一个之后，就会变成后手的状态，等待对方挑选后我再变成先手。
        // g为后手选择的最优解
        int caseL = num[l] + g(num,l+1,r);
        int caseR = num[r] + g(num,l,r-1);
        // 作为先手，我可以挑选最大的那个
        return Math.max(caseL,caseR);
    }

	// 对于同一个情况来说的后手视角
    public static int g(int[] num, int l,int r){
        // 只有一张牌我还是后手，所以我没有选择
        if(l==r){
            return 0;
        }
        // 如果对方挑了L位置的数，相当于我在L+1和R之间是先手了
        // 对面会给我最小的那个情况
        int caseL =  f(num,l+1,r);
        int caseR =  f(num,l,r-1);
        return Math.min(caseL,caseR);
    }

记忆化搜索：

    // 对于同一个情况来说的先手视角//    
	public static int f(int[] num, int l,int r,int[][] fmap,int [][]gmap){
        if(fmap[l][r] != -1){
            return fmap[l][r];
        }
        int ans = 0;
        if(l==r){
            ans = num[r];
        }else{
            int caseL = num[l] + g(num,l+1,r,fmap,gmap);
            int caseR = num[r] + g(num,l,r-1,fmap,gmap);
            ans = Math.max(caseL,caseR);
        }
        fmap[l][r] = ans;
        return ans;
    }

// 对于同一个情况来说的后手视角
    public static int g(int[] num, int l,int r,int[][] fmap,int [][]gmap){
        if(gmap[l][r] != -1){
            return gmap[l][r];
        }
        int ans = 0;
       if(l != r){
           int caseL =  f(num,l+1,r,fmap,gmap);
           int caseR =  f(num,l,r-1,fmap,gmap);
           ans = Math.min(caseL,caseR);
       }
        gmap[l][r] = ans;
        return ans;
    }

动态规划

   public static int dp(int[] arr) {

        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
        }
        for (int startCol = 1; startCol < N; startCol++) {
            int L = 0;
            int R = startCol;
            while (R < N) {
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }

16.3 数字字符转字符串

1. 题目

规定：1对应A ，2对应B， 3对应C，依此类推，26对应Z。

那么一个数字字符串比如111就可以转化为AAA KA AK。

给定一个只有数字字符组成的字符串nums返回有多少种转化结果。

2. 思路

暴力递归：对于从idx开始的数，往下扩展多少呢？用个for代表扩展的上限（或因为长度为1或者2，直接分开讨论即可）。

记忆化搜索和动态规划直接就抄就好了。

3. 代码

判断合法：

private static boolean isLigal(String str, int idx, int i) {
    StringBuffer sb = new StringBuffer();
    sb.append(str,idx,i+1);
    String s = sb.toString();
    int num = Integer.parseInt(s);
    if(num > 0 && num <= 26) return true;
    return false;
}

递归：

    public static int dfs(int idx,String str){
        int n = str.length();
        if(idx == n){
            return 1;
        }
        int sum = 0;
        for(int i = idx; i < n; i++){
            if(!isLigal(str,idx,i)) break;
            sum += dfs(i+1,str);
        }
        return sum;
    }

记忆化搜索：

private static int memorizedSearch(int idx, String str, int[] dp) {
    if(dp[idx] != 0) return dp[idx];
    int n = str.length();
    if(idx == n){
        dp[idx] = 1;
        return 1;
    }
    int sum = 0;
    for(int i = idx; i < n; i++){
        if(!isLigal(str,idx,i)) break;
        sum += dfs(i+1,str);
    }
    dp[idx] = sum;
    return dp[idx];
}

动态规划 ：

private static int dynamicPlanning(String str) {
    int len = str.length();
    int[] dp = new int[len+1];
    dp[len] = 1;
    // 因为跟idx+1有关，所以从后往前
    for (int idx = len-1; idx >= 0; idx--) {
        int sum = 0;
        for(int i = idx; i < len; i++){
            if(!isLigal(str,idx,i)) break;
            sum += dp[i+1];
        }
        dp[idx] = sum;
    }
    return dp[0];
}

16.4 最长公共子序列

1. 题目

https://leetcode-cn.com/problems/longest-common-subsequence/

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

2. 思路

暴力递归：

1. 如果当前的i，j都是子序列的值，那么i++，j++。
2. 如果i是，j不是，那么j++。
3. 反之，i++。

记忆化搜索：直接转换

动态规划：注意依赖右，下，右下角，完善即可。

3. 代码

暴力：

    // 在0-n范围内
    public int process(char[] str1, char[] str2,int i, int j,int[][]dp){
        if(i == str1.length) return 0;
        if(j == str2.length) return 0;
        if(dp[i][j] != -1) return dp[i][j];
        if(str1[i] == str2[j]){
            return 1 + process(str1,str2,i+1,j+1,dp);
        }
        // 12不等
        int p1 = process(str1,str2,i+1,j,dp);
        int p2 = process(str1,str2,i,j+1,dp);
        dp[i][j] = Math.max(p1,p2);
        return dp[i][j];
    }

动态规划：

    public int dynamicPlanning(char[] str1, char[] str2){
        int len1 = str1.length;
        int len2 = str2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i < dp.length; i++){
            Arrays.fill(dp[i],-1);
        }

        for(int i = 0; i < dp.length; i++) dp[i][len2] = 0;
        for(int i = 0; i < dp[0].length; i++) dp[len1][i] = 0;

        // 从右下角开始
        for(int i = len1-1; i >= 0; i--){
            for(int j = len2-1; j >= 0; j--){
                if(str1[i] == str2[j]) {
                    dp[i][j] = 1 + dp[i+1][j+1];
                    continue;
                }
                    
                int p1 = dp[i+1][j];
                int p2 = dp[i][j+1];
                dp[i][j] = Math.max(p1,p2);
            }
        }
        return dp[0][0];
    }

16.5 最长回文子序列

1. 题目

https://leetcode.cn/problems/longest-palindromic-subsequence/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

2. 思路

方法1：类似于最长公共子序列，只需要自己和自己的翻转找最长公共子序列即可。

方法2：定义递归为求从 i 到 j 之间的最长回文子序列。

​ 如果 i j 相等，长度为1。如果 i , j 相邻并且相等，长度为2。其他情况下，如果ij相等，长度为2，并且开始递归i-1,j-1。不等可以考虑删掉某一个（因为左右不等二者删掉一个的时候一定有一个是有正解在的。

​ 记忆化搜索好改，动态规划，注意依赖的是左下，画表填充即可。

3. 代码

class Solution {
    int[][] dp ;
    public int longestPalindromeSubseq(String s) {
        char[] str = s.toCharArray();
        if(str.length == 0) return 0;
        dp = new int[str.length][str.length];
        // int ans = process(str,0,str.length-1);
        int ans = dynamicPlanning(str);
        return ans;
    }
    // 求[0,n-1]中的回文
    public int process(char[] str,int l, int r){
        if(l >= str.length || r < 0) return 0;
        if(dp[l][r] != 0) return dp[l][r];
        if(l == r) {
            dp[l][r] = 1;
            return 1;
        }
        // 注意这里的1，而不是0，
        // 因为这句话的含义是只剩下两个节点的情况下,要么相等，长度为2，要么不等长度为单个字符-1
        // 注意：l==r不能作废，防止只有一个值的情况 r-1越界
        if(l == r-1 && str[l] == str[r]){
            dp[l][r] = 2;
            return 2;
        }
        
        if(str[l] == str[r]) return 2 + process(str,l+1,r-1);
        // 保留l，保留r
        int p1 = process(str,l,r-1);
        int p2 = process(str,l+1,r);
        dp[l][r] = Math.max(p1,p2);
        return dp[l][r];
    }
    /**
        aba
             0 1 2 i
           0 1 0 0
           1 0 1 0
           2 0 0 1
           j 
     */
    public int dynamicPlanning(char[] str){
        int len = str.length;
        for(int i = 0; i < len; i++) dp[i][i] = 1;
        for(int i = 0; i < len-1; i++) dp[i][i+1] =  str[i] == str[i+1] ? 2 : 1; 
        // print();
        for(int l = len-3; l >= 0; l--){
            for(int r = l+1; r < len; r++){
                if(str[l] == str[r]){
                    dp[l][r] = 2 + dp[l+1][r-1];
                    continue;
                }
                int p1 = dp[l][r-1];
                int p2 = dp[l+1][r];
                dp[l][r] = Math.max(p1,p2);
            }
        }
        return dp[0][len-1];
    }
    public void print(){
        for(int i = 0; i < dp.length; i++){
            System.out.println(Arrays.toString(dp[i]));
        }
    }

}

16.6 马的位置

1. 题目

假设象棋棋盘的最左下角是(0,0)位置那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域给你三个参数x, y. k
返回“马”从(0.0)位置出发，必须走k步最后落在(xy)上的方法数有多少种?

2. 思路

正常的递归，但是动态规划是三维的，需要注意。

16.7 01背包问题

16.7.1 经典背包问题

1. 题目

给你两个数组，一个是重量数组weight，一个是价值数组value，二者长度都为N，还有一个背包能装下的最大重量bag。求背包可装下的最大价值。

2. 思路

暴力递归：

​ 01背包也就是对于某一个位置的值选/不选的问题。可以理解为子集型回溯。需要注意的是，边界条件的返回值应该是什么？0，因为到头后没有价值。

记忆化搜索和动态规划直接就抄就好了。

3. 代码

暴力递归：

private static int process(int[] weight, int[] value, int idx, int rest) {
    // 注意：为什么是0
    if(idx == weight.length) return 0;
    // 不选
    int p1 = process(weight,value,idx+1,rest);
    // 选
    int p2 = -1;
    if(rest - weight[idx] >= 0)
        p2 = value[idx] + process(weight, value, idx+1, rest-weight[idx]);
    return Math.max(p1,p2);
}

记忆化搜索：

private static int memorizedSearch(int[] weight, int[] value, int idx, int rest,int[][] dp) {
    // 注意：为什么是0
    if(idx == weight.length){
        return 0;
    }
    if(dp[idx][rest] != 0) return dp[idx][rest];
    // 不选
    int p1 = process(weight,value,idx+1,rest);
    // 选
    int p2 = -1;
    if(rest - weight[idx] >= 0)
        p2 = value[idx] + process(weight, value, idx+1, rest-weight[idx]);
    dp[idx][rest] = Math.max(p1,p2);
    return dp[idx][rest];
}

动态规划 ：

    public static int dynamicPlanning(int[] weight, int[] value,int bag){
        int[][]dp = new int[weight.length][bag+1];
        // idx依赖于idx+1
        // 从后往前遍历
        for(int idx = dp.length-2; idx >= 0; idx--){
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[idx+1][rest];
                int p2 = -1;
                if(rest - weight[idx] >= 0)
                    p2 = value[idx] + dp[idx+1][rest-weight[idx]];
                dp[idx][rest] = Math.max(p1,p2);
            }
        }
        return dp[0][bag];
    }

16.7.2 目标和

1. 题目

https://leetcode.cn/problems/target-sum/

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

2. 思路

常规的选/不选方式似乎不行，因为target为负数，可以考虑只选正数其他都是负数的情况下，有所有正数的和p，总数sum，目标target。他们的关系为p-(sum-p) = target，也就是说，p = (sum+target)/2，当p等于这个数的时候，就是我们要的条件。

注意：因此sum+target必须是偶数

而后套用01背包即可。

注意1：dfs的时候判断边界条件一定是val == target && idx == nums.length因为有可能有值为0的情况，那么就可以随便拿。

注意2：空间优化的时候，遍历方向

3.代码

递归：

public int dfs(int idx, int val, int target,int[] nums){
    // 边界条件
    if(val == target && idx == nums.length) return 1;
    if(idx == nums.length) return 0;
    // 两种情况，选不选
    int p1 = dfs(idx+1,val,target,nums);
    int p2 = 0;
    if(val + nums[idx] <= target) p2 = dfs(idx+1,val+nums[idx],target,nums);
    // 返回相加
    return p1 + p2;
}

动态规划1：

public int dynamicPlanning0(int sum, int target,int[] nums){
    int m = nums.length+1;
    int n = target+1;
    int[][] dp = new int[m][n];
    dp[m-1][target] = 1;
    for(int i = m-2; i >= 0; i--){
        for(int j = n-1; j >= 0; j--){
            int p1 = dp[i+1][j];
            int p2 = 0;
            if(j + nums[i] <= target) p2 = dp[i+1][j+nums[i]];
            dp[i][j] = p1 + p2;
        }
    }
    return dp[0][0];
}

动态规划2：空间优化

public int dynamicPlanning(int sum, int target,int[] nums){
    int m = nums.length+1;
    int n = target+1;
    int[] dp = new int[n];
    dp[target] = 1;
    for(int i = m-2; i >= 0; i--){
        // 必须从前往后遍历，不然更新p2的时候，dp[j+nums[i]]已经被更改了
        for(int j = 0; j < n; j++){
            int p1 = dp[j];
            int p2 = 0;
            if(j + nums[i] <= target) p2 = dp[j+nums[i]];
            dp[j] = p1 + p2;
        }
    }
    return dp[0];
}

16.8 无表结构的动态规划

如果没有固定的表结构，可能无法得到状态转移数组，所以只能 回溯 -> 记忆化搜索，而不能进一步的得到动态规划的值。

16.2.1 贴纸拼词

1. 题目

https://leetcode.cn/problems/stickers-to-spell-word/

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：

输入： stickers = ["with","example","science"], target = "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入：stickers = ["notice","possible"], target = "basicbasic"
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

2. 思路

暴力递归1：我们可以依次尝试用sticks[i] 作为第一张，target剩下什么。

暴力递归2：在1的基础上，我们直接把String[n]转为int[n] [26]的频率数组，而后进行加减。

记忆化搜索：我们发现，变量是String，没办法声明一个数组，记录变化，只能生成一个HashMap<String,Integer> 其中String代表剩余字符串的样子，Integer代表对于这个字符串，我们曾经生成过的结果。如果rest在HashMap中，说明我们算过了，直接返回结果。

3. 代码

暴力1生成target剩下的rest：

	public static String minus(String s1, String s2) {
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		int[] count = new int[26];
		// 统计str1
		for (char cha : str1) {
			count[cha - 'a']++;
		}
		
		// 统计str2，负数无所谓
		for (char cha : str2) {
			count[cha - 'a']--;
		}
		
		// 不大于0不添加
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < 26; i++) {
			if (count[i] > 0) {
				for (int j = 0; j < count[i]; j++) {
					builder.append((char) (i + 'a'));
				}
			}
		}
		return builder.toString();
	}

暴力递归1：

public static int process1(String[] stickers, String target) {
   if (target.length() == 0) {
      return 0;
   }
   int min = Integer.MAX_VALUE;
   for (String first : stickers) {
      String rest = minus(target, first);
      // 如果没有正向收益
      if (rest.length() != target.length()) {
         min = Math.min(min, process1(stickers, rest));
      }
   }
   return min + (min == Integer.MAX_VALUE ? 0 : 1);
}

暴力递归2字符串变成频率数组：

public static int minStickers2(String[] stickers, String target) {
   int N = stickers.length;
   // 关键优化(用词频表替代贴纸数组)
   int[][] counts = new int[N][26];
   for (int i = 0; i < N; i++) {
      char[] str = stickers[i].toCharArray();
      for (char cha : str) {
         counts[i][cha - 'a']++;
      }
   }
   int ans = process2(counts, target);
   return ans == Integer.MAX_VALUE ? -1 : ans;
}

暴力递归2主体：

// stickers[i] 数组，当初i号贴纸的字符统计 int[][] stickers -> 所有的贴纸
// 每一种贴纸都有无穷张
// 返回搞定target的最少张数
// 最少张数
public static int process2(int[][] stickers, String t) {
   if (t.length() == 0) {
      return 0;
   }
   // target做出词频统计
   // target  aabbc  2 2 1..
   //                0 1 2..
   char[] target = t.toCharArray();
   int[] tcounts = new int[26];
   for (char cha : target) {
      tcounts[cha - 'a']++;
   }
   int N = stickers.length;
   int min = Integer.MAX_VALUE;
   for (int i = 0; i < N; i++) {
      // 尝试第一张贴纸是谁
      int[] sticker = stickers[i];
      // 最关键的优化(重要的剪枝!这一步也是贪心!)
      // target[0]-'a' : 比如'b'-'a' = 1 也就是sticker频率数组所在的位置。
      // 一定选一个可以消掉第一个字符（或者任意一个，但是第一个好找）的数（如果不行，那么未必能优化）
      if (sticker[target[0] - 'a'] > 0) {
         StringBuilder builder = new StringBuilder();
         for (int j = 0; j < 26; j++) {
            if (tcounts[j] > 0) {
               int nums = tcounts[j] - sticker[j];
               for (int k = 0; k < nums; k++) {
                  builder.append((char) (j + 'a'));
               }
            }
         }
         String rest = builder.toString();
         min = Math.min(min, process2(stickers, rest));
      }
   }
   return min + (min == Integer.MAX_VALUE ? 0 : 1);
}

记忆化搜索：加入字符串

public static int minStickers3(String[] stickers, String target) {
   int N = stickers.length;
   int[][] counts = new int[N][26];
   for (int i = 0; i < N; i++) {
      char[] str = stickers[i].toCharArray();
      for (char cha : str) {
         counts[i][cha - 'a']++;
      }
   }
   HashMap<String, Integer> dp = new HashMap<>();
   // 为空不需要算了，一定是0
   dp.put("", 0);
   int ans = process3(counts, target, dp);
   return ans == Integer.MAX_VALUE ? -1 : ans;
}

记忆化搜索主体：

public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
   if (dp.containsKey(t)) {
      return dp.get(t);
   }
   char[] target = t.toCharArray();
   int[] tcounts = new int[26];
   for (char cha : target) {
      tcounts[cha - 'a']++;
   }
   int N = stickers.length;
   int min = Integer.MAX_VALUE;
   for (int i = 0; i < N; i++) {
      int[] sticker = stickers[i];
      if (sticker[target[0] - 'a'] > 0) {
         StringBuilder builder = new StringBuilder();
         for (int j = 0; j < 26; j++) {
            if (tcounts[j] > 0) {
               int nums = tcounts[j] - sticker[j];
               for (int k = 0; k < nums; k++) {
                  builder.append((char) (j + 'a'));
               }
            }
         }
         String rest = builder.toString();
         min = Math.min(min, process3(stickers, rest, dp));
      }
   }
   int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
   dp.put(t, ans);
   return ans;
}

16.9 可优化的动态规划

一般来说，如果在dfs中出现了遍历的情况，可以考虑进行二次优化，看遍历能不能用某种公式替代，比如，dp[i] [j]可能是前3个数之和，那么dp[i] [j] = dp[i] [j-1] - dp[i] [j-1] 多的往前数第四个数 + 缺的那个数。类似于滑动窗口一样。

dp[i] [j] = dp[i] [j-1] - dp[i] [j-1-k] + nums[i] [j]

16.3.1 将字符串反转到单调递增

1. 题目

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

示例 1：

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

2. 思路

暴力递归：

​ 分为四种情况：

1. 当前为0的情况

   a) 0不动，那么idx自动加1不需要其他操作

   b) 0改成1，那么后续的值都需要为1，所需的答案为从idx到最后中0的个数

2. 当前为1的情况

​ a) 把1改成0，翻转次数+1

​ b) 1不动，那么后续的值都需要为1，所需的答案为从idx到最后中0的个数

以此得到dfs1

而通过观察发现，01两种大情况，只有a) 有一点点不一样，可以合并，得到好看的dfs2。

动态规划1：

​ 根据dfs2的依赖关系得到动态规划方程，但是里面嵌套循环，时间复杂度n2，在两万的数据中不太能接受（其实java能过）。

动态规划2时间减少：

​ 发现p2和我们的动态规划似乎没关系，可以单独留一个数组用来保存p2需要的值。这样就是n的复杂度了。

动态规划3：空间减少

​ 可以发现dp[i]只依赖于dp[i+1]，zero[i] 只依赖于zero[i+1]，所以一个变量保存。

3. 代码

暴力递归：

// 保证idx前面都是0
    public int dfs(char[] str, int idx) {
        if(idx == str.length) return 0;
        int ans = 0;
        // 由下面的注释合并而来
        int p1 = dfs(str,idx+1) + (str[idx] == '0' ? 0 : 1);
        int p2 = 0;   
        for(int i = idx; i < str.length; i++)
            if(str[i] == '0') p2++;
        ans = Math.min(p1,p2);
        return ans;

        // 发现这两个只差一点不一样，合并
        // if(str[idx] == '0') {
        //     // 1. 0不动
        //     int p1 = dfs(str,idx+1);
        //     // 2. 0改成1
        //     int p2 = 0;   // p2就是从他开始往后0的个数
        //     for(int i = idx; i < str.length; i++)
        //         if(str[i] == '0') p2++;
        //     ans = Math.min(p1,p2);
        // }else{
        //     // 1. 选择把他改成0
        //     int p1 = 1 + dfs(str,idx+1);
        //     // 2. 不改了，从他往后都是1
        //     int p2 = 0;   // p2就是从他开始往后0的个数
        //     for(int i = idx; i < str.length; i++)
        //         if(str[i] == '0') p2++;
        //     // System.out.println(p1+" "+p2);
        //     ans = Math.min(p1,p2);
        // }

    }

动态规划1：

    public int dp1(char[] str){
        int[] dp = new int[str.length+1];
        int len = dp.length;
        dp[str.length] = 0;
        for(int idx = str.length-1; idx >= 0; idx--){
            int p1 = dp[idx+1] + (str[idx] == '0'?0:1);
            int p2 = 0;
            // 这里发现和dp没有关系，所以单独尝试优化：
            // 方法：建立一个数组来保存[idx,str.length)中0出现的次数
            for(int i = idx; i < str.length; i++)
                if(str[i] == '0') p2++;
            dp[idx] = Math.min(p1,p2);
        }
        return dp[0];
    }

动态规划2：

    public int dp2(char[] str){
        int[] dp = new int[str.length+1];
        int[] zero = new int[str.length];
        if(str[str.length-1] == '0') zero[str.length-1] = 1;
        
        for(int i = zero.length-2; i >= 0; i--){
            zero[i] = zero[i+1] + (str[i] == '0' ? 1 : 0);
        }
        int len = dp.length;
        dp[str.length] = 0;
        // 时间上可以了，但是空间能不能优化？
        for(int idx = str.length-1; idx >= 0; idx--){
            int p1 = dp[idx+1] + (str[idx] == '0'?0:1);
            int p2 = zero[idx];
            dp[idx] = Math.min(p1,p2);
        }
        return dp[0];
    }

动态规划3：

    public int dp3(char[] str){
        int dp = 0;
        int zero = 0;
        for(int idx = str.length-1; idx >= 0; idx--){
            dp = dp + (str[idx] == '0'?0 : 1);
            zero = zero + (str[idx] == '0'?1 : 0); // 边界注意
            dp = Math.min(dp,zero);
        }
        return dp;
    }

16.10 状态压缩的动态规划

有时候我们递归的值可能是一个一维的数组，数组代表比如我们是否选择一个数，当数组小于32的时候，可以用状态压缩：也就是让我们的32位以下的二进制01组合成一个数，压缩状态。

16.？ 换根DP

1. 题目

现有n个编号为0~n-1的锂电池，以一颗树的形式组织连接起来对于其中的任何一个锂电池，定义其供电难度为该锂电池到其他所有锂电池的距离之和(树状结构中每条连接线的长度记为1)。给定一个树形组织的锂电池组，公司需要求出每个电池的供电难度来判断最佳供电位置。
n的范围是3*10^4，

第一行输入n，表示电池的数量接下来输入n-1行整数，每一行有两个整数和，表示编号为的锂电池和编号为的锂电池相连

示例1

输入：
	n = 6
	voltage = [[0,1],[0,2],[2,3],[2,4],[2,5]];
输出：[8, 12, 6, 10, 10, 10]

2. 思路

假设我们随便选a开头，有一个多叉树：

通过第一次遍历，我们可以得到的结果：

1. 每个子树包括多少节点

比如p就有1个节点，d有2个，b有5个，分别是bdefp。

2. 子树到自己需要的总距离

p到d距离为1

d以及他的子树一起到b距离，累加为：1（p到d的距离）+1（代价）+1（1代表d到b的距离）= 3。

e到 b的距离为1，f到b的距离为1。

所以b的后代到b的总距离为3（p,d）+ 1 (d)+1(b) = 5。

同理，c = 3。

所有节点到a的距离 = 5（所有节点到b的花费） + 5（左侧子节点数，有这么多个节点需要+1）

​ +3 （所有节点到c的花费）+ 4（右侧子节点数，有这么多个节点需要+ 1）

而后对应每一个节点，比如说b节点，我们可以发现，如果把b当成头的话，b的原本的子节点到自己的距离不变。

而原本的根a(包括他的子树c)去掉b后的距离就是 : a作为根时候的总距离 - b的花费 - 曾经b为根时候的节点 。

把这个当成新的a之后，就有：

b为根的总距离 = 所有节点到a的花费 + a的子节点个数 + 原本b子节点到b的花费。

以此类推，以O(N)的复杂度，得到了结果。

3. 代码

class Solution {
    int[] ans;
    int[] sz;
    int[] dp;
    List<List<Integer>> graph;

    public int[] sumOfDistancesInTree(int n, int[][] edges) {
        // 距离
        ans = new int[n];
        // 子树的数量
        sz = new int[n];
        // dp[u]:以 u为根的子树，它的所有子节点到它的距离之和
        dp = new int[n];
        graph = new ArrayList<List<Integer>>();
        // idx为节点信息，值为子节点信息
        for (int i = 0; i < n; ++i) {
            graph.add(new ArrayList<Integer>());
        }
        for (int[] edge: edges) {
            int u = edge[0], v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        dfs(0, -1);
        dfs2(0, -1);
        return ans;
    }

    public void dfs(int u, int f) {
        sz[u] = 1;
        dp[u] = 0;
        for (int v: graph.get(u)) {
            if (v == f) {
                continue;
            }
            dfs(v, u);
            dp[u] += dp[v] + sz[v];
            sz[u] += sz[v];
        }
    }

    public void dfs2(int u, int f) {
        ans[u] = dp[u];
        for (int v: graph.get(u)) {
            if (v == f) {
                continue;
            }
            int pu = dp[u], pv = dp[v];
            int su = sz[u], sv = sz[v];

            dp[u] -= dp[v] + sz[v];
            sz[u] -= sz[v];
            dp[v] += dp[u] + sz[u];
            sz[v] += sz[u];

            dfs2(v, u);

            dp[u] = pu;
            dp[v] = pv;
            sz[u] = su;
            sz[v] = sv;
        }
    }
}

标签：return,idx,16,int,length,str,动态,规划,dp
From： https://www.cnblogs.com/ylw-blogs/p/17818898.html