//思路：
// 当模式中的第二个字符不是“*”时：
// 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
// 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
//
// 当模式中的第二个字符是“*”时：
// 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
// 如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
// 1、模式后移2字符，相当于x*被忽略；
// 2、字符串后移1字符，模式后移2字符；(匹配一位)
// 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
public boolean match(char[] str, char[] pattern) {
if(str==null || pattern==null){
return false;
}
return match(str,0,pattern,0);
}
private boolean match(char[] str,int strIndex,char[] pattern,int patternIndex){
if(strIndex==str.length && patternIndex==pattern.length){
// str 和 pattern 都到达了末尾，则返回 true
return true;
}
if(patternIndex==pattern.length && strIndex!=str.length){
//pattern 先到达了末尾，则返回 false
return false;
}
//当模式中的第二个字符不是“*”时：
if(patternIndex+1<pattern.length && pattern[patternIndex+1]=='*'){
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
(strIndex != str.length && pattern[patternIndex] == '.')){
return match(str,strIndex,pattern,patternIndex+2) ||
//1、模式后移2字符，相当于x*被忽略；
match(str,strIndex+1,pattern,patternIndex+2) ||
// 2、字符串后移1字符，模式后移2字符；(匹配一位)
match(str,strIndex+1,pattern,patternIndex);
// 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位
}else{ // 前一个元素既不相等，也不是"*",模式后移 2 字符，相当于 x* 被忽略。
return match(str,strIndex,pattern,patternIndex+2);
}
}else{
// 如果字符串第一个字符和模式中的第一个字符相匹配，
// 那么字符串和模式都后移一个字符，然后匹配剩余的。
if((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
(pattern[patternIndex] == '.' && strIndex != str.length)){
return match(str,strIndex+1,pattern,patternIndex+1);
}else{
return false;
}
}
}//解法一：
public int Fibonacci(int n) {
if (n <= 1)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}//解法二：是对解法一的优化
public int Fibonacci(int n) {
if (n <= 1)
return n;
int pre1 = 0, pre2 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre1 + pre2;
pre1 = pre2;
pre2 = fib;
}
return fib;
}public int JumpFloor(int target) {
if(target<=2){
return target;
}
int pre1 = 1;
int pre2 = 2;
for(int i=3;i<=target;i++){
int next = pre1 + pre2;
pre1 = pre2;
pre2 = next;
}
return pre2;
}//思路一：
// 公式法
// 跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去... ，那么
// f(n) = f(n-1) + f(n-2) + ... + f(0) (I)
// 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么
// f(n-1) = f(n-2) + f(n-3) + ... + f(0) (II)
// (I) - (II) 式，可得
// f(n) - f(n-1) = f(n-1)
// 即
//f(n) = 2*f(n-1)
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}//思路二：
//动态规划：dp[i] 表示跳上 i 级别的台阶总共的跳法
//思路一种 f(n) = 2*f(n-1)
//这里就是 dp[i] = 2*dp[i-1]
public int JumpFloorII(int target) {
if(target<=1){
return target;
}
//dp[i] 表示跳上 i 级别的台阶总共的跳法
int[] dp = new int[target+1];
Arrays.fill(dp,1);
for(int i=2;i<=target;i++){
dp[i] = 2*dp[i-1];
}
return dp[target];
}public int RectCover(int target) {
if (target==1){
return 1;
}
if(target==2){
return 2;
}
int pre1 = 1;
int pre2 = 2;
int res = 0;
for(int i=3;i<=target;i++){
res = pre1 + pre2;
pre1 = pre2;
pre2 = res;
}
return res;
}//思路：
//动态规划思路
//dp[i] 表示以 array[i] 结尾的元素连续子数组的最大连续和
//dp[i-1]>0 时，dp[i] = dp[i-1] + array[i]
//否则，dp[i] = array[i]//写法一：
//时间复杂度：O(n)
//空间复杂度：O(n)
//连续子数组的最大和
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int n = array.length;
//dp[i] 表示以array[i]结尾的元素连续子数组的最大连续和
int[] dp = new int[n];
dp[0] = array[0];
int res= Integer.MIN_VALUE;
for(int i=1;i<n;i++){
if(dp[i-1]>0){
dp[i] =dp[i-1]+array[i]; //array[i] 加上任意一个 > 0 的数都会大于原来的数
}else{
dp[i] = array[i];
}
res = Math.max(res,dp[i]);
}
return res;
}//写法二:
//时间复杂度：O(n)
//空间复杂度：O(1)
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int n = array.length;
int pre1 = array[0];
int res= Integer.MIN_VALUE;
for(int i=1;i<n;i++){
int pre2 = (pre1>0)?(pre1+array[i]):array[i];
pre1 = pre2;
res = Math.max(res,pre2);
}
return res;
}//思路：
//第一个是 1，接下来可以是 1 * 2 , 1 * 3 , 1 * 5，此时最小的显然是 2
//第二个是 2，接下来可以是 2 * 2 , 2 * 3 , 2 * 5，此时就要把这次得到的三个 4,6,10 和上一次剩下的两个3,5 比较大小，找出最小的，即 3
//第三个是 3，接下来可以是 3 * 2 , 3 * 3 , 3 * 5
//...
public int GetUglyNumber_Solution(int index) {
if(index<=1){
return index;
}
int[] dp = new int[index+1];
dp[1] = 1;
int i2 = 1, i3 = 1, i5 = 1;
for(int i=2;i<=index;i++){
int next2=dp[i2]*2;
int next3=dp[i3]*3;
int next5=dp[i5]*5;
dp[i] = min3(next2,next3,next5);
if(dp[i]==next2){
i2++;
}
if(dp[i]==next3){
i3++;
}
if(dp[i]==next5){
i5++;
}
}
return dp[index];
}
private int min3(int a,int b,int c){
int tmp = a<b?a:b;
return (tmp<c)?tmp:c;
}//思路：
//动态规划
//dp[i] 表示将 i 分割成几个整数的最大成乘积和
public int cutRope(int target) {
int n=target;
if(n==1){
return 0;
}
//dp[i] 表示将 i 分割成几个整数的最大成乘积和
int[] dp = new int[n+1];
dp[1] = 0;
dp[2] = 1;
for(int i=3;i<=n;i++){
for(int j=1;j<i;j++){
dp[i] = max3(dp[i],j*(i-j),j*dp[i-j]);
}
}
return dp[n];
}
private int max3(int a,int b,int c){
int tmp=a>b?a:b;
return tmp>c?tmp:c;
}
@Test
public void test(){
int n=10;
System.out.println(integerBreak(n));
}public int getMost(int[][] board) {
int m=board.length;
int n=board[0].length;
//dp[i][j] 到 board 位置的最大价值
int[][] dp=new int[m][n];
dp[0][0]=board[0][0];
for(int j=1;j<n;j++){
dp[0][j] = dp[0][j-1] + board[0][j];
}
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + board[i][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+board[i][j];
}
}
return dp[m-1][n-1];
}扔 n 个骰子，向上面的数字之和为 S。给定 n，请列出所有可能的 S 值及其相应的概率。
举例
举例 1：
输入：n = 1
输出：[[1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
解释：掷一次骰子，向上的数字和可能为1,2,3,4,5,6，出现的概率均为 0.17。
举例 2：
输入：n = 2
输出：[[2,0.03],[3,0.06],[4,0.08],[5,0.11],[6,0.14],[7,0.17],[8,0.14],[9,0.11],[10,0.08],[11,0.06],[12,0.03]]
解释：掷两次骰子，向上的数字和可能在[2,12]，出现的概率是不同的。
//思路：
//dp[i][j] 表示扔 i 个骰子，向上面的数字之和为 j 出现的次数
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
final int faces = 6;
final int num = faces*n; //n 个骰子向上的数字和的最大值
// dp[i][j] 表示扔 i 个骰子，向上面的数字之和为 j 出现的次数
long[][] dp=new long[faces+1][num+1];
//只有一个骰子
for(int j=1;j<=faces;j++){
dp[1][j] = 1;
}
//扔 i 个骰子
for(int i=2;i<=n;i++){
for(int j=i;j<=num;j++){
// i 的骰子的数字和最小为 i（和最小的情况，就是这 i 个骰子向上的值都为 1）
for(int k=1;k<=faces && k<=j;k++){
dp[i][j] += dp[i-1][j-k];
}
}
}
final double totalNum = Math.pow(6,n);
//总共有 totalNum 中可能的数字和
//统计频率
Map<Integer,Double> records = new HashMap<>();
for(int j=n;j<=num;j++){
records.put(j,dp[n][j]/totalNum);
}
return new ArrayList<>(records.entrySet());
}//思路：
//动态规划：dp[i] 表示字符串 s 的前 i 个字符解码的个数
//注意：遇到 '0' 字符是不能解码的
public int numDecodings(String s) {
if(s==null || s.length()==0){
return 0;
}
int n =s.length();
int[] dp = new int[n+1];
dp[0]=1; // 没有字符则只有一种解码方式
dp[1]=s.charAt(0)=='0'?0:1; //字符 '0',不能进行解码
for(int i=2;i<=n;i++){
//解码一位字符
int one = Integer.parseInt(s.substring(i-1,i));
if(one!=0){
dp[i] += dp[i-1];
}
if(s.charAt(i-2)=='0'){ ////字符 '0',不能进行解码
continue;
}
int two=Integer.parseInt(s.substring(i-2,i));
if(two<=26){
dp[i] += dp[i-2];
}
}
return dp[n];
}最长公共子序列问题（Longest Common Subsequence，LCS）：
给出两个字符串 S1 和 S2，求这两个字符串的最长公共子序列。
比如：s1=ABCD, s2=AEBD 的最长公共子序列为[ABD]
//思路：
// 状态： LCS(m,n) 为 S1[0...m] 和 S2[0...n] 的最长公共子序列
// 状态转移方程：
// 当 S1[m] == S2[n] 时，LCS(m,n)= 1 + LCS(m-1,n-1);
// 当 S1[m] != S2[n] 时，LCS(m,n)=max{LCS(m,n-1),LCS(m-1,n)}
public int LCS(String s,String t){
int m=s.length();
int n=t.length();
if(m==0 || n==0){
return 0;
}
//lcs[i][j] 表示 s[0...i] 和 t[0...j] 之间的最长公共子序列长度
int[][] lcs=new int[m+1][n+1];
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
lcs[i][j]=0;
}
}
/**
* 当 S1[m] == S2[n] 时，LCS(m,n)= 1 + LCS(m-1,n-1);
* 当 S1[m] != S2[n] 时，LCS(m,n)=max{LCS(m,n-1),LCS(m-1,n)}
**/
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s.charAt(i-1)==t.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
}else{
lcs[i][j]=Math.max(lcs[i-1][j],lcs[i][j-1]);
}
}
}
return lcs[m][n];
}private char[][] x;
//x[i][j]=='c' 表示斜方向
//x[i][j]=='u' 表示向上
//x[i][j]=='l' 表示向左
private StringBuilder res;
public int LCS(String s,String t){
int m=s.length();
int n=t.length();
if(m==0 || n==0){
return 0;
}
//lcs[i][j] 表示 s[0...i] 和 t[0...j] 之间的最长公共子序列长度
int[][] lcs=new int[m+1][n+1];
x=new char[m+1][n+1];
res=new StringBuilder();
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
lcs[i][j]=0;
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s.charAt(i-1)==t.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
x[i][j]='c';
}else if(lcs[i-1][j]>=lcs[i][j-1]){
lcs[i][j]=lcs[i-1][j];
x[i][j]='u';
}else if(lcs[i-1][j]<lcs[i][j-1]){
lcs[i][j]=lcs[i][j-1];
x[i][j]='l';
}
}
}
return lcs[m][n];
}
public void print(String s,int m,int n){
if(m==0 || n==0){
return;
}
if(x[m][n]=='c'){
print(s,m-1,n-1);
res.append(s.charAt(m-1));
}else if(x[m][n]=='l'){
print(s,m,n-1);
}else if(x[m][n]=='u'){
print(s,m-1,n);
}
}public int minDistance(String word1, String word2) {
int m=word1.length();
int n=word2.length();
if(m==0){ // word2 中的每个元素都需要删除
return n;
}
if(n==0){ // word1 中的每个元素都需要删除
return m;
}
int[][] lcs=new int[m+1][n+1];
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
lcs[i][j]=0;
}
}
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
}else{
lcs[i][j]=Math.max(lcs[i-1][j],lcs[i][j-1]);
}
}
}
return (m+n-2*lcs[m][n]);
}//思路一：
//什么是子序列？不包括该序列本身
//什么是上升？后一个元素大于前一个元素
//一个序列可能有多个最长上升子序列？但是最长长度是唯一的。
//动态规划思路：dp[i] 表示以 nums[i] 结尾的最长上升子序列
//时间复杂度：O(n^2)
public int lengthOfLIS(int[] nums) {
int n=nums.length;
if(n==0){
return 0;
}
//dp[i] 表示以 nums[i] 结尾的最长上升子序列
//最长上升子序列的最小长度是 1
//if(nums[i]>nums[j])
// LIS(i)=max(j<i){1+LCS(j) }
int[] dp=new int[n];
for(int i=0;i<n;i++){
dp[i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){ //上升子序列
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
}
int res=1; //最长上升子序列的最小长度是 1
for(int i=0;i<n;i++){
res=Math.max(res,dp[i]);
}
return res;
}//思路二：
// 定义一个 tails 数组，其中 tails[i] 存储长度为 i + 1 的最长递增子序列的最后一个元素。
// 对于一个元素 x，
// 如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x。
// 如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1；
// 例如对于数组 [4,3,6,5]，有：
// tails len num
// [] 0 4
// [4] 1 3
// [3] 1 6
// [3,6] 2 5
// [3,5] 2 null
// tails 数组保持有序，因此在查找 x 位于 tails 数组的位置时就可以使用二分查找。
//时间复杂度：O(nlogn)
public int lengthOfLIS(int[] nums) {
int n=nums.length;
if(n==0){
return 0;
}
//tails[i] 存储长度为 i + 1 的最长递增子序列的最后一个元素
int[] tails=new int[n];
int len=0;
for(int x:nums){
//x 大于 tails 数组所有的值时，i=len
int i=binarySearch(tails,0,len,x);
// 不管是 tails[i-1] < x <= tails[i]，更新 tails[i] 为 x；
// 还是 x 大于 tails 数组所有的值,将 x 添加到 tails 后面
// 都使用 tails[i]=x;
tails[i]=x;
if(i==len){ // 大于 tails 数组所有的值，最长递增子序列长度加 1
len++;
}
}
return len;
}
//tail[l,r) 二分查找 key 元素
private int binarySearch(int[] tails,int l,int r,int key){
while(l<r){
int mid=(r-l)/2+l;
if(tails[mid]==key){
return mid;
}else if(tails[mid]>key){
r=mid;
}else{
assert tails[mid]<key;
l=mid+1;
}
}
return l;
}