class066 一维动态规划【算法】

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;
  }
}

[3,4,9,20,50,...]
 0 1 2 3 4
 1天 1天 1天 1天 f(4,)
      7天   1天 f(4,)
      30天      f(4,)

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];
  }
}

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;
  }
}

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;
  }
}

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];
  }
}

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;
  }
}

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;
  }
}

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;
  }
}