最长有效括号
32：给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
class Solution {public int longestValidParentheses(String s) {int length = s.length();if(length<2)return 0;//以s[i]个字符结尾的最长有效括号int[] dp = new int[s.length()];dp[0]=0;int max =0;for(int i=1;i<length;i++){if(s.charAt(i)==')'){//判断s[1]if(i==1&&s.charAt(0)=='(')dp[i]=2;else{//s[2]-s[length-1]if(s.charAt(i-1)=='(')//前一个是左括号，立马匹配dp[i]=dp[i-2]+2;else{//前面的右括号有效匹配的起始点是：(i-1-dp[i-1])+1 因此再与i-1-dp[i-1]看能否匹配int index = i-1-dp[i-1];if(index>=0&&s.charAt(index)=='('){if(index==0)dp[i]=dp[i-1]+2;elsedp[i]=dp[i-1]+dp[index-1]+2;}}}max = Math.max(max,dp[i]);}}return max;}
}解码
91：解码方法
class Solution {int result=0;public int numDecodings(String s) {int length = s.length();int[] dp = new int[length];if(s.charAt(0)=='0'){dp[0]=0;}else{dp[0]=1;}for(int i=1;i<length;i++){//当前元素不为0if(s.charAt(i)!='0'){//当前元素单独作为一个字母dp[i]=dp[i-1];}//是否和前面一个元素作为一个字母if(s.charAt(i-1)!='0'){int tmp = Integer.parseInt(s.substring(i-1,i+1));if(tmp>=1&&tmp<=26){if(i>=2)dp[i] += dp[i-2];elsedp[i] ++;}}}return dp[length-1];}
}整数拆分/剪绳子
343/剑指offer14
class Solution {public int cuttingRope(int n) {int[] dp = new int[n+1];dp[2] = 1;for(int i =3; i<=n; i++){for(int j = 1; j<i-1; j++){dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));}}return dp[n];}
}