asdasdsada
//枚举
class Solution {
//满足条件的个数
int sumCount = 0;
public int findTargetSumWays(int[] nums, int target) {
calculate(nums, target , 0 , 0);
return sumCount;
}
public void calculate(int[] nums , int target , int curVal , int i){
if(i == nums.length){
if(curVal == target)
sumCount++;
}else{
calculate(nums , target , curVal+nums[i] , i+1);
calculate(nums , target , curVal-nums[i] , i+1);
}
}
}
//动态规划思想：找边界，转移方程
//设置dp[i][j],表示前i个数，组成和为j的方案书
//转移方程: dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
//换成递推思想：dp[i][j-nums[i]] += dp[i-1][j] , dp[i][j+nums[i]] +=dp[i-1][j]
//但是注意边界思想
class Solution {
public static int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int i = 0; i < nums.length; i++)
sum += nums[i];
// 绝对值范围超过了sum的绝对值范围则无法得到
if (Math.abs(s) > Math.abs(sum)) return 0;
int len = nums.length;
int range = sum * 2 + 1;//因为要包含负数所以要两倍，又要加上0这个中间的那个情况
int[][] dp = new int[len][range];//这个数组是从总和为-sum开始的
//加上sum纯粹是因为下标界限问题，赋第二维的值的时候都要加上sum
// 初始化 第一个数只能分别组成+-nums[i]的一种情况
// 注意如果nums[0] =0,则对应dp[0][sum] =2
dp[0][sum + nums[0]] += 1;
dp[0][sum - nums[0]] += 1;
for (int i = 1; i < len; i++) {
for (int j = -sum; j <= sum; j++) {
if((j+nums[i]) > sum) {//+不成立 加上当前数大于了sum 只能减去当前的数
dp[i][j+sum] = dp[i-1][j-nums[i]+sum]+0;
}else if((j-nums[i]) < -sum) {//-不成立 减去当前数小于-sum 只能加上当前的数
dp[i][j+sum] = dp[i-1][j+nums[i]+sum]+0;
}else {//+-都可以
dp[i][j+sum] = dp[i-1][j+nums[i]+sum]+dp[i-1][j-nums[i]+sum];
}
}
}
return dp[len - 1][sum + s];
}
}
asdasdsada
/*动态规划 时间复杂度O(mn) 空间复杂度(mn)
p去匹配s，当两个一个为空，都是false，然后写边界(不过题中已经给出长度限制，所以不为空)
dp[i][j]代表p的前j个字符匹配s的前i个
边界：dp[0][j]匹配空字符串，只有x*x*X*X*这样的情况才是true
转移方程：先考虑当前
s.charAt(i-1)和p.charAt(j-1)相等的时候 dp[i][j]=dp[i-1][j-1] 这是相等的情况 （还有字符不相等的时候）
字符不相等有三种情况：
p.chgarAt(j-1)属于a~z，但是p.charAt(j-1)!=s.charAt(i-1) 这时候dp[i][j]=false；不需要考虑
p.charAt(j-1)='.' , dp[i][j] = dp[i-1][j-1]
p.charAt(j-1)='*' 这时候要考虑'*'如何匹配，0个或者多个
0个：*取0，例子：ab abc* --->判断 ab是否等于ab即可，即dp[i][j]=dp[i][j-2]，
1个：*取1，例子：abb abb* ----->这时候如果s.charAt(i-1)=p.charAt(j-2),这时候*取1，则dp[i][j]=dp[i-1][j]
多个(其实通过递推思想就相当于1个)：*取多个 例子：abbbbbbb ab*------>这时候看p的前j个字符匹配s的前i-1个即可，
也就是dp[i][j] =dp[i-1][j],比如这种情况*取了3，那dp[i-1][j] = dp[i-2][j]这种*取了2，直到*取了0，也就是上一种情况,因此没必要单独写
还有p.charAt(j-1) ='*'的情况下如果p.charAt(j-2)='.'例子：ab ab.*,
.*可以匹配任何字符串，因此p的前j个字符能匹配s的前i-1个即可 dp[i][j] = dp[i-1][j]
dp[i][j] = dp[i-1][j]
*/
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen+1][pLen+1];
//边界
dp[0][0] = true;
for(int j = 2 ; j<=pLen ; j+=2){
if(p.charAt(j-1) == '*'){
dp[0][j] = dp[0][j-2];
}
}
//考虑转移方程
for(int i=1 ; i<=sLen ; i++){
for(int j=1 ; j<=pLen ; j++){
//首先是字母的情况
int sCurChar = s.charAt(i-1);
int pCurChar = p.charAt(j-1);
if(sCurChar == pCurChar || pCurChar == '.'){
dp[i][j] = dp[i-1][j-1];
}else if(pCurChar == '*'){
if(dp[i][j-2]){
dp[i][j] = dp[i][j-2];
}else if(sCurChar == p.charAt(j-2) || p.charAt(j-2) == '.'){
dp[i][j] = dp[i-1][j];
}
}
}
}
return dp[sLen][pLen];
}
}