刷题记录

思路 ： 满足条件有2种情况 1. s1前i个和s2前i个是scramble string, s1后len-i个和s2后len-i个是scramble string 2. s1前i个和s2后i个是scramble string, s1后len-i个和s2前len-i个是scramble string 可以用递归来做: if(isScramble(s1.substring(0,i),s2.substring(0,i))&& isScramble(s1.substring(i),s2.substring(i))) return true; if(isScramble(s1.substring(0,i),s2.substring(s2.length()-i))&& isScramble(s1.substring(i),s2.substring(0,s2.length()-i))) return true; 实现： 有一个巧妙的方式来判断在2个string长度一样的时候是否字符都匹配。如下： int[] letters=new int[26]; for(int i=0;i<s1.length();i++) { letters[s1.charAt(i)-'a']++; letters[s2.charAt(i)-'a']--; } for(int i=0;i<26;i++) { if(letters[i]!=0) return false; }

思路 ： 几乎和stone game一模一样。因为允许circle，所以在这里扩展一次数组。比如[4,4,5,9]，就变成了[4,4,5,9,4,4,5,9]。区间还是1~n。 实现 ： 所求得的最终结果是每个区间的最小值。

思路： 一开始以为是stone game的马甲，结果情况更复杂。 transition : dp[i][j]=Max(dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1])， i<=k<=j。dp[i][j]表示在i到j这个区间(inclusive)打气球得到的最大值。而k表示，最后一个打第k个气球的情况。比如[4,1,5,5]，最后一个打1，那么[4]和[5,5]都打完了，打1的时候的值就是1*1*1，不包括边界(exclusive)。 实现细节： 这里需要把第-1个和第n+1个2个为1的气球放进数组里。所以需要一个新的长度为n+2的数组。

思路： state: dp[i][j]代表从第i个石头到第j个石头，能堆的最小cost。 transition: dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[i][j]), i<=k<j。s[i][j]是拆分后最后一步需要的cost。 initial value: dp[i][i]=0 实现细节：取最小值循环前，应该赋给当前dp最大值。