代码随想三刷动态规划篇4
- 494. 目标和
- 题目
- 代码
- 474. 一和零
- 题目
- 代码
- 518. 零钱兑换 II
- 题目
- 代码
494. 目标和
题目
链接
代码
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i =0;i<nums.length;i++){
sum+=nums[i];
}
if(sum<Math.abs(target)){
return 0;
}
if((sum-target)%2==1){
return 0;
}
int subNum = (sum-target)/2;
int[] dp = new int[subNum+1];
dp[0] = 1;
for(int i =0;i<nums.length;i++){
for(int j = dp.length-1;j>=nums[i];j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[subNum];
}
}
474. 一和零
题目
链接
代码
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//dp[i][j] 0为i个,1为j个,的最大子集数
int[][] dp = new int[m+1][n+1];
for(int k =0;k<strs.length;k++){
int[] MN = countMN(strs[k]);
for(int i =m;i>=MN[0];i--){
for(int j =n;j>=MN[1];j--){
dp[i][j] = Math.max(dp[i][j],dp[i-MN[0]][j-MN[1]]+1);
}
}
}
return dp[m][n];
}
public int[] countMN(String str){
char[] arr = str.toCharArray();
int m = 0;
int n = 0;
for(int i =0;i<arr.length;i++){
if(arr[i]=='0'){
m++;
}else{
n++;
}
}
return new int[]{m,n};
}
}
518. 零钱兑换 II
题目
链接
代码
class Solution {
public int change(int amount, int[] coins) {
int dp[] = new int[amount+1];
dp[0] = 1;
for(int i = 0;i<coins.length;i++){
for(int j=coins[i];j<=dp.length-1;j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}