动态规划 - 一打木

动态规划问题的一般形式就是求最值

求解动态规划的核心问题是穷举

把大的问题细化到一个点，先研究在这个小的点上如何解决问题，然后再通过递归/迭代的方式扩展到整个问题

定义 dp 数组/函数的含义 -> 明确 base case -> 明确「状态」-> 明确「选择」

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

可以用数学归纳的思想来简单理解动态规划：

子序列问题

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度

base case：dp[i] 初始值为 1，

dp[i]怎么推出dp[i+1]：比num[i]小的子序列加1中最长的

完整代码

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp,1);
    int res = 0;
    for(int i =0;i<nums.length;i++){
        for(int j =0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }
        res = Math.max(dp[i],res);
    }
    return res;
}

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

定义：nums[0..i] 中的「最大的子数组和」为 dp[i]

这样是不行的，无法从dp[i]推出dp[i+1]，因为不确定nums[0..i] 中的最大子数组与num[i+1]相邻

定义：以 nums[i] 为结尾的「最大子数组和」为 dp[i]

base case：dp[0] = num[0]

dp[i]怎么推出dp[i+1]：dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

完整代码

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int res = dp[0];
    for(int i=1;i<nums.length;i++){
        dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);
        res = Math.max(res,dp[i]);
    }
    return res;
}

最长公共子序列

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

[!IMPORTANT]
对于两个字符串求子序列的问题，都是用两个指针 i 和 j 分别在两个字符串上移动，大概率是动态规划思路

定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i] [j]

base case: dp[0] [..] = dp[..] [0] = 0

怎么得到dp[i] [j]：

s1[i-1] == s2[j-1] ， dp[i] [j] = 1 + dp[i - 1] [j - 1];
s1[i-1] != s2[j-1] ， dp[i] [j] = Math.max(dp[i] [j - 1], dp[i - 1] [j]);

完整代码

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m+1][n+1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    return dp[m][n];
}

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

定义：s1[0..i-1] 和 s2[0..j-1] 的编辑距离为 dp[i] [j]

base case: dp[0] [..] = dp[..] [0] = 0

怎么得到dp[i] [j]：

s1[i-1] == s2[j-1] ， dp[i] [j] = dp[i - 1] [j - 1];
s1[i-1] != s2[j-1] ，

          dp[i][j] = min(
               dp[i - 1][j] + 1, //删除
               dp[i][j - 1] + 1, //添加
               dp[i - 1][j - 1] + 1 //替换
                        
);

完整代码

  int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]
    int[][] dp = new int[m + 1][n + 1];
    // base case 
    for (int i = 1; i <= m; i++)
        dp[i][0] = i;
    for (int j = 1; j <= n; j++)
        dp[0][j] = j;
    // 自底向上求解
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(
                    dp[i - 1][j] + 1, //删除

                    dp[i][j - 1] + 1, //插入

                    dp[i - 1][j - 1] + 1 //替换

                );
            }
        }
    }
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

最长回文子序列

>给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 > >子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

定义：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]

base case：dp[i] [j] = 1，dp[i > j] = 0

怎么得到dp[i] [j] ：

if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

完整代码

    
int longestPalindromeSubseq(String s) {
    int n = s.length();
    // dp 数组全部初始化为 0
    int[][] dp = new int[n][n];
    // base case
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    // 反着遍历保证正确的状态转移
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; 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]);
            }
        }
    }
    // 整个 s 的最长回文子串长度
    return dp[0][n - 1];
}

子序列问题总结

一个字符串常用一维dp数组：

比如最长递增子序列和最大子数组和都是这个思路

在这个思路中 dp 数组的定义是：

在子数组 arr[0..i] 中，以 arr[i] 结尾的子序列的长度是 dp[i]

两个字符串或者回文字符串常用二维dp数组： 比如最长公共子序列和编辑距离及最长回文子序列

在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列长度为 dp[i][j]

在子数组 array[i..j] 中，我们要求的子序列的长度为 dp[i][j]

背包类型问题

0-1背包问题

输入：
PYTHON
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
输出最大价值

定义：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]

base case： dp[0] [..] = dp[..] [0] = 0

怎么推出dp [i] [w] ：

dp[i][w] = max(
            dp[i-1][w], //不装背包
            dp[i-1][w - wt[i-1]] + val[i-1] //装背包
        )

完整代码

int knapsack(int W, int N, int[] wt, int[] val) {
    assert N == wt.length;
    // base case 已初始化
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }
    
    return dp[N][W];
}

子集背包问题

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

先对集合求和，得出 sum，把问题转化为背包问题：

给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

定义：dp[i] [j] 表示，对于前 i 个物品，当前背包的容量为 j 时，若值为 true，则说明可以恰好将背包装满

base case： dp[..] [0] = true ， dp[0] [..] = false

怎么得到dp[i] [j] ： dp[i] [j] = dp[i - 1] [j] || dp[i - 1] [j - nums[i - 1]]; 装或者不装有一个为true即为true

完整代码

boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    // 和为奇数时，不可能划分成两个和相等的集合
    if (sum % 2 != 0) return false;
    int n = nums.length;
    sum = sum / 2;
    boolean[][] dp = new boolean[n + 1][sum + 1];
    // base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j - nums[i - 1] < 0) {
                // 背包容量不足，不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j];
            } else {
                // 装入或不装入背包
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][sum];
}

给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2

定义： dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包

base case： dp[0] [..] = 0 ， dp[0] [0] = 1 ，dp[1..n] [0] 不一定就一种

怎么推出dp[i] [j] ： dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];

完整代码

int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    // 这两种情况，不可能存在合法的子集划分
    if (sum < Math.abs(target) || (sum + target) % 2 == 1) {
        return 0;
    }
    return subsets(nums, (sum + target) / 2);
}

int subsets(int[] nums, int sum) {
    int n = nums.length;
    int[][] dp = new int[n + 1][sum + 1];
    // base case
    dp[0][0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
            if (j >= nums[i-1]) {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            } else {
                // 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
}

完全背包问题

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。

背包问题的描述形式：

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

定义： dp[i][j] ：若只使用前 i 个物品（可以重复使用），当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包

base case ： dp[0][..] = 0, dp[..][0] = 1

怎么推出dp[i] [j] ： dp[i][j] = dp[i - 1][j] + dp[i][j-coins[i-1]];

完整代码

int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];
    // base case
    for (int i = 0; i <= n; i++) 
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++)
            if (j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j] 
                         + dp[i][j - coins[i-1]];
            else 
                dp[i][j] = dp[i - 1][j];
    }
    return dp[n][amount];
}

打家劫舍问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

定义： dp[i] = x 表示：从第 i 间房子开始抢劫，最多能抢到的钱为 x

base case ： dp [n], dp [n+1] 为 0 没有房间可以抢劫

怎么推出dp [i] ： dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]); 抢或者不抢

完整代码：

public int rob(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n + 2];
        
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
    }

    return dp[0];
}

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

同打家劫舍，因为环形，相当于nums[0...n-2] 和 nums[1...n-1] 即不抢第一家和不抢最后一家的最大值

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) {
        return nums[0];
    }
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

public int robRange(int[] nums, int start, int end) {
    int n = nums.length;
    int[] dp = new int[n + 2];

    for (int i = end; i >= start; i--) {
        dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
    }

    return dp[start];
}

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 *在不触动警报的情况下，小偷能够盗取的最高金额* 。

定义： dp(node) 抢这个节点

base case ：节点为null ，抢的为0

怎么推：抢这个节点和不抢这个节点的最大值 res = Math.max(root.val + not, res); not 为抢下下层节点的值的和

Map<TreeNode, Integer> memo = new HashMap<>();

public int rob(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (memo.containsKey(root)) 
        return memo.get(root);
    //不抢
    int not = 0;
    if (root.left != null) {
        not += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        not += rob(root.right.left) + rob(root.right.right);
    }
    //抢
    int res = rob(root.left) + rob(root.right);

    res = Math.max(root.val + not, res);
    memo.put(root,res);

    return res;

}