class066 一维动态规划
code1 509斐波那契数列
// 斐波那契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 也就是：F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
// 给定 n ，请计算 F(n)
// 测试链接 : https://leetcode.cn/problems/fibonacci-number/
// 注意：最优解来自矩阵快速幂，时间复杂度可以做到O(log n)
// 后续课程一定会讲述！本节课不涉及！
dp[i]：从F(i)的值
=1,i=1
=i+dp[i-1],i>=2
f1 递归
f2 从顶到底 记忆化搜索
f3 从底到顶
f4 空间优化
package class066; import java.util.Arrays; // 斐波那契数 // 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 // 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。 // 也就是：F(0) = 0，F(1) = 1 // F(n) = F(n - 1) + F(n - 2)，其中 n > 1 // 给定 n ，请计算 F(n) // 测试链接 : https://leetcode.cn/problems/fibonacci-number/ // 注意：最优解来自矩阵快速幂，时间复杂度可以做到O(log n) // 后续课程一定会讲述！本节课不涉及！ public class Code01_FibonacciNumber { public static int fib1(int n) { return f1(n); } public static int f1(int i) { if (i == 0) { return 0; } if (i == 1) { return 1; } return f1(i - 1) + f1(i - 2); } public static int fib2(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, -1); return f2(n, dp); } public static int f2(int i, int[] dp) { if (i == 0) { return 0; } if (i == 1) { return 1; } if (dp[i] != -1) { return dp[i]; } int ans = f2(i - 1, dp) + f2(i - 2, dp); dp[i] = ans; return ans; } public static int fib3(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } int[] dp = new int[n + 1]; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } public static int fib4(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } int lastLast = 0, last = 1; for (int i = 2, cur; i <= n; i++) { cur = lastLast + last; lastLast = last; last = cur; } return last; } }
code2 983最低票价
// 最低票价
// 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
// 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
// 每一项是一个从 1 到 365 的整数
// 火车票有 三种不同的销售方式
// 一张 为期1天 的通行证售价为 costs[0] 美元
// 一张 为期7天 的通行证售价为 costs[1] 美元
// 一张 为期30天 的通行证售价为 costs[2] 美元
// 通行证允许数天无限制的旅行
// 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
// 那么我们可以连着旅行 7 天(第2~8天)
// 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
// 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
dp[i]:以i…天的最低票价
=math.min(cost[k]+dp[j]),(k:3种方案，j:方案到期天数)
f1 递归 有重复调用
[3,4,9,20,50,...] 0 1 2 3 4 1天 1天 1天 1天 f(4,) 7天 1天 f(4,) 30天 f(4,)
f2 记忆化搜索 带缓存的搜索
f3 动态规划
package class066; import java.util.Arrays; // 最低票价 // 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行 // 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出 // 每一项是一个从 1 到 365 的整数 // 火车票有 三种不同的销售方式 // 一张 为期1天 的通行证售价为 costs[0] 美元 // 一张 为期7天 的通行证售价为 costs[1] 美元 // 一张 为期30天 的通行证售价为 costs[2] 美元 // 通行证允许数天无限制的旅行 // 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证 // 那么我们可以连着旅行 7 天(第2~8天) // 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 // 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/ public class Code02_MinimumCostForTickets { // 无论提交什么方法都带着这个数组 0 1 2 public static int[] durations = { 1, 7, 30 }; // 暴力尝试 public static int mincostTickets1(int[] days, int[] costs) { return f1(days, costs, 0); } // days[i..... 最少花费是多少 public static int f1(int[] days, int[] costs, int i) { if (i == days.length) { // 后续已经无旅行了 return 0; } // i下标 : 第days[i]天，有一场旅行 // i.... 最少花费是多少 int ans = Integer.MAX_VALUE; for (int k = 0, j = i; k < 3; k++) { // k是方案编号 : 0 1 2 while (j < days.length && days[i] + durations[k] > days[j]) { // 因为方案2持续的天数最多，30天 // 所以while循环最多执行30次 // 枚举行为可以认为是O(1) j++; } ans = Math.min(ans, costs[k] + f1(days, costs, j)); } return ans; } // 暴力尝试改记忆化搜索 // 从顶到底的动态规划 public static int mincostTickets2(int[] days, int[] costs) { int[] dp = new int[days.length]; for (int i = 0; i < days.length; i++) { dp[i] = Integer.MAX_VALUE; } return f2(days, costs, 0, dp); } public static int f2(int[] days, int[] costs, int i, int[] dp) { if (i == days.length) { return 0; } if (dp[i] != Integer.MAX_VALUE) { return dp[i]; } int ans = Integer.MAX_VALUE; for (int k = 0, j = i; k < 3; k++) { while (j < days.length && days[i] + durations[k] > days[j]) { j++; } ans = Math.min(ans, costs[k] + f2(days, costs, j, dp)); } dp[i] = ans; return ans; } // 严格位置依赖的动态规划 // 从底到顶的动态规划 public static int MAXN = 366; public static int[] dp = new int[MAXN]; public static int mincostTickets3(int[] days, int[] costs) { int n = days.length; Arrays.fill(dp, 0, n + 1, Integer.MAX_VALUE); dp[n] = 0; for (int i = n - 1; i >= 0; i--) { for (int k = 0, j = i; k < 3; k++) { while (j < days.length && days[i] + durations[k] > days[j]) { j++; } dp[i] = Math.min(dp[i], costs[k] + dp[j]); } } return dp[0]; } }
code3 91解码方法
// 解码方法
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// ‘A’ -> “1”
// ‘B’ -> “2”
// …
// ‘Z’ -> “26”
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
// 例如，“11106” 可以映射为：“AAJF”、“KJF”
// 注意，消息不能分组为(1 11 06)，因为 “06” 不能映射为 “F”
// 这是由于 “6” 和 “06” 在映射中并不等价
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
// 题目数据保证答案肯定是一个 32位 的整数
// 测试链接 : https://leetcode.cn/problems/decode-ways/
dp[i]：以i开始的[i…]的解码方法个数
=0,s[i]==‘0’
=dp[i+1]+1
+=dp[i+2],s[i] s[i+1]构成合法解码
f1 递归
f2 记忆化搜索
f3 动态规划
package class066; import java.util.Arrays; // 解码方法 // 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ： // 'A' -> "1" // 'B' -> "2" // ... // 'Z' -> "26" // 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法） // 例如，"11106" 可以映射为："AAJF"、"KJF" // 注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F" // 这是由于 "6" 和 "06" 在映射中并不等价 // 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 // 题目数据保证答案肯定是一个 32位 的整数 // 测试链接 : https://leetcode.cn/problems/decode-ways/ public class Code03_DecodeWays { // 暴力尝试 public static int numDecodings1(String s) { return f1(s.toCharArray(), 0); } // s : 数字字符串 // s[i....]有多少种有效的转化方案 public static int f1(char[] s, int i) { if (i == s.length) { return 1; } int ans; if (s[i] == '0') { ans = 0; } else { ans = f1(s, i + 1); if (i + 1 < s.length && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26) { ans += f1(s, i + 2); } } return ans; } // 暴力尝试改记忆化搜索 public static int numDecodings2(String s) { int[] dp = new int[s.length()]; Arrays.fill(dp, -1); return f2(s.toCharArray(), 0, dp); } public static int f2(char[] s, int i, int[] dp) { if (i == s.length) { return 1; } if (dp[i] != -1) { return dp[i]; } int ans; if (s[i] == '0') { ans = 0; } else { ans = f2(s, i + 1, dp); if (i + 1 < s.length && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26) { ans += f2(s, i + 2, dp); } } dp[i] = ans; return ans; } // 严格位置依赖的动态规划 public static int numDecodings3(String str) { char[] s = str.toCharArray(); int n = s.length; int[] dp = new int[n + 1]; dp[n] = 1; for (int i = n - 1; i >= 0; i--) { if (s[i] == '0') { dp[i] = 0; } else { dp[i] = dp[i + 1]; if (i + 1 < s.length && ((s[i] - '0') * 10 + s[i + 1] - '0') <= 26) { dp[i] += dp[i + 2]; } } } return dp[0]; } // 严格位置依赖的动态规划 + 空间压缩 public static int numDecodings4(String s) { // dp[i+1] int next = 1; // dp[i+2] int nextNext = 0; for (int i = s.length() - 1, cur; i >= 0; i--) { if (s.charAt(i) == '0') { cur = 0; } else { cur = next; if (i + 1 < s.length() && ((s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0') <= 26) { cur += nextNext; } } nextNext = next; next = cur; } return next; } }
code4 639解码方法 II
// 解码方法 II
// 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
// ‘A’ -> “1”
// ‘B’ -> “2”
// …
// ‘Z’ -> “26”
// 要 解码 一条已编码的消息，所有的数字都必须分组
// 然后按原来的编码方案反向映射回字母（可能存在多种方式）
// 例如，“11106” 可以映射为：“AAJF”、“KJF”
// 注意，像 (1 11 06) 这样的分组是无效的，“06"不可以映射为’F’
// 除了上面描述的数字字母映射方案，编码消息中可能包含 '’ 字符
// 可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括 ‘0’）
// 例如，"1” 可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19”
// 对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息
// 给你一个字符串 s ，由数字和 ‘*’ 字符组成，返回 解码 该字符串的方法 数目
// 由于答案数目可能非常大，返回10^9 + 7的模
// 测试链接 : https://leetcode.cn/problems/decode-ways-ii/
dp[i]：以i开始的[i…]的解码方法个数
=0,s[i]= =‘0’
=dp[i+1]x9,s[i]==‘*’
+=dp[i+2],s[i] s[i+1]构成合法解码
f1 递归
f2 记忆化搜索
package class066; import java.util.Arrays; // 解码方法 II // 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ： // 'A' -> "1" // 'B' -> "2" // ... // 'Z' -> "26" // 要 解码 一条已编码的消息，所有的数字都必须分组 // 然后按原来的编码方案反向映射回字母（可能存在多种方式） // 例如，"11106" 可以映射为："AAJF"、"KJF" // 注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F' // 除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符 // 可以表示从 '1' 到 '9' 的任一数字（不包括 '0'） // 例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" // 对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息 // 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 // 由于答案数目可能非常大，返回10^9 + 7的模 // 测试链接 : https://leetcode.cn/problems/decode-ways-ii/ public class Code04_DecodeWaysII { // 没有取模逻辑 // 最自然的暴力尝试 public static int numDecodings1(String str) { return f1(str.toCharArray(), 0); } // s[i....] 有多少种有效转化 public static int f1(char[] s, int i) { if (i == s.length) { return 1; } if (s[i] == '0') { return 0; } // s[i] != '0' // 2) i想单独转 int ans = f1(s, i + 1) * (s[i] == '*' ? 9 : 1); // 3) i i+1 一起转化 <= 26 if (i + 1 < s.length) { // 有i+1位置 if (s[i] != '*') { if (s[i + 1] != '*') { // num num // i i+1 if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) { ans += f1(s, i + 2); } } else { // num * // i i+1 if (s[i] == '1') { ans += f1(s, i + 2) * 9; } if (s[i] == '2') { ans += f1(s, i + 2) * 6; } } } else { if (s[i + 1] != '*') { // * num // i i+1 if (s[i + 1] <= '6') { ans += f1(s, i + 2) * 2; } else { ans += f1(s, i + 2); } } else { // * * // i i+1 // 11 12 ... 19 21 22 ... 26 -> 一共15种可能 // 没有10、20，因为*只能变1~9，并不包括0 ans += f1(s, i + 2) * 15; } } } return ans; } public static long mod = 1000000007; public static int numDecodings2(String str) { char[] s = str.toCharArray(); long[] dp = new long[s.length]; Arrays.fill(dp, -1); return (int) f2(s, 0, dp); } public static long f2(char[] s, int i, long[] dp) { if (i == s.length) { return 1; } if (s[i] == '0') { return 0; } if (dp[i] != -1) { return dp[i]; } long ans = f2(s, i + 1, dp) * (s[i] == '*' ? 9 : 1); if (i + 1 < s.length) { if (s[i] != '*') { if (s[i + 1] != '*') { if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) { ans += f2(s, i + 2, dp); } } else { if (s[i] == '1') { ans += f2(s, i + 2, dp) * 9; } if (s[i] == '2') { ans += f2(s, i + 2, dp) * 6; } } } else { if (s[i + 1] != '*') { if (s[i + 1] <= '6') { ans += f2(s, i + 2, dp) * 2; } else { ans += f2(s, i + 2, dp); } } else { ans += f2(s, i + 2, dp) * 15; } } } ans %= mod; dp[i] = ans; return ans; } public static int numDecodings3(String str) { char[] s = str.toCharArray(); int n = s.length; long[] dp = new long[n + 1]; dp[n] = 1; for (int i = n - 1; i >= 0; i--) { if (s[i] != '0') { dp[i] = (s[i] == '*' ? 9 : 1) * dp[i + 1]; if (i + 1 < n) { if (s[i] != '*') { if (s[i + 1] != '*') { if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) { dp[i] += dp[i + 2]; } } else { if (s[i] == '1') { dp[i] += dp[i + 2] * 9; } if (s[i] == '2') { dp[i] += dp[i + 2] * 6; } } } else { if (s[i + 1] != '*') { if (s[i + 1] <= '6') { dp[i] += dp[i + 2] * 2; } else { dp[i] += dp[i + 2]; } } else { dp[i] += dp[i + 2] * 15; } } } dp[i] %= mod; } } return (int) dp[0]; } public static int numDecodings4(String str) { char[] s = str.toCharArray(); int n = s.length; long cur = 0, next = 1, nextNext = 0; for (int i = n - 1; i >= 0; i--) { if (s[i] != '0') { cur = (s[i] == '*' ? 9 : 1) * next; if (i + 1 < n) { if (s[i] != '*') { if (s[i + 1] != '*') { if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) { cur += nextNext; } } else { if (s[i] == '1') { cur += nextNext * 9; } if (s[i] == '2') { cur += nextNext * 6; } } } else { if (s[i + 1] != '*') { if (s[i + 1] <= '6') { cur += nextNext * 2; } else { cur += nextNext; } } else { cur += nextNext * 15; } } } cur %= mod; } nextNext = next; next = cur; cur = 0; } return (int) next; } }
code5 264. 丑数 II
// 丑数 II
// 给你一个整数 n ，请你找出并返回第 n 个 丑数
// 丑数 就是只包含质因数 2、3 或 5 的正整数
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
dp[i]：保存数据
[i2]:x2的指针
[i3]:x3的指针
[i5]:x5的指针
f0 就是现有子集 *2 *3 *5运算得到后续结果
f1 动态规划
package class066; // 丑数 II // 给你一个整数 n ，请你找出并返回第 n 个 丑数 // 丑数 就是只包含质因数 2、3 或 5 的正整数 // 测试链接 : https://leetcode.cn/problems/ugly-number-ii/ public class Code05_UglyNumberII { // 时间复杂度O(n)，n代表第n个丑数 public static int nthUglyNumber(int n) { // dp 0 1 2 ... n // 1 2 ... ? int[] dp = new int[n + 1]; dp[1] = 1; for (int i = 2, i2 = 1, i3 = 1, i5 = 1, a, b, c, cur; i <= n; i++) { a = dp[i2] * 2; b = dp[i3] * 3; c = dp[i5] * 5; cur = Math.min(Math.min(a, b), c); if (cur == a) { i2++; } if (cur == b) { i3++; } if (cur == c) { i5++; } dp[i] = cur; } return dp[n]; } }
code6 32. 最长有效括号
// 最长有效括号
// 给你一个只包含 ‘(’ 和 ‘)’ 的字符串
// 找出最长有效（格式正确且连续）括号子串的长度。
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
dp[i]：以s[i]结尾构成的最长有效括号的长度
=0,s[i]= =‘(’
=dp[p-1]+dp[i-1]+2 s[p]= =‘(’&&s[i]==‘)’
p=i-dp[i-1]-1
f 动态规划
package class066; // 最长有效括号 // 给你一个只包含 '(' 和 ')' 的字符串 // 找出最长有效（格式正确且连续）括号子串的长度。 // 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/ public class Code06_LongestValidParentheses { // 时间复杂度O(n)，n是str字符串的长度 public static int longestValidParentheses(String str) { char[] s = str.toCharArray(); // dp[0...n-1] // dp[i] : 子串必须以i位置的字符结尾的情况下，往左整体有效的最大长度 int[] dp = new int[s.length]; int ans = 0; for (int i = 1, p; i < s.length; i++) { if (s[i] == ')') { p = i - dp[i - 1] - 1; // ? ) // p i if (p >= 0 && s[p] == '(') { dp[i] = dp[i - 1] + 2 + (p - 1 >= 0 ? dp[p - 1] : 0); } } ans = Math.max(ans, dp[i]); } return ans; } }
code7 67. 环绕字符串中唯一的子字符串
// 环绕字符串中唯一的子字符串
// 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串
// 所以 base 看起来是这样的：
// “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
dp[?] 以?结尾的子字符串的长度，?26个字母
ans=∑dp(0<=i<26)
f 动态规划
package class066; // 环绕字符串中唯一的子字符串 // 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串 // 所以 base 看起来是这样的： // "..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.." // 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现 // 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/ public class Code07_UniqueSubstringsWraparoundString { // 时间复杂度O(n)，n是字符串s的长度，字符串base长度为正无穷 public static int findSubstringInWraproundString(String str) { int n = str.length(); int[] s = new int[n]; // abcde...z -> 0, 1, 2, 3, 4....25 for (int i = 0; i < n; i++) { s[i] = str.charAt(i) - 'a'; } // dp[0] : s中必须以'a'的子串，最大延伸长度是多少，延伸一定要跟据base串的规则 int[] dp = new int[26]; // s : c d e.... // 2 3 4 dp[s[0]] = 1; for (int i = 1, cur, pre, len = 1; i < n; i++) { cur = s[i]; pre = s[i - 1]; // pre cur if ((pre == 25 && cur == 0) || pre + 1 == cur) { // (前一个字符是'z' && 当前字符是'a') || 前一个字符比当前字符的ascii码少1 len++; } else { len = 1; } dp[cur] = Math.max(dp[cur], len); } int ans = 0; for (int i = 0; i < 26; i++) { ans += dp[i]; } return ans; } }
code8 940. 不同的子序列 II
// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
f 动态规划
package class066; // 不同的子序列 II // 给定一个字符串 s，计算 s 的 不同非空子序列 的个数 // 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 // 字符串的 子序列 是经由原字符串删除一些（也可能不删除） // 字符但不改变剩余字符相对位置的一个新字符串 // 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是 // 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/ public class Code08_DistinctSubsequencesII { // 时间复杂度O(n)，n是字符串s的长度 public static int distinctSubseqII(String s) { int mod = 1000000007; char[] str = s.toCharArray(); int[] cnt = new int[26]; int all = 1, newAdd; for (char x : str) { newAdd = (all - cnt[x - 'a'] + mod) % mod; cnt[x - 'a'] = (cnt[x - 'a'] + newAdd) % mod; all = (all + newAdd) % mod; } return (all - 1 + mod) % mod; } }
