acwing-3. 完全背包问题
acwing-3. 完全背包问题
12345678910111213141516171819202122232425262728import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int w = sc.nextInt(); int[] weight = new int[n+1]; int[] value = new int[n+1]; for(int i = 1; i<= n; i++){ weight[i] = sc.nextInt(); value[i] = sc.nextInt(); } System.out.print(getMax(n, w, weig ...
acwing-2. 01背包问题
acwing-2. 01背包问题
二维数组dp
12345678910111213141516171819202122232425262728293031import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] w = new int[N + 1]; int[] value = new int[N + 1]; for(int i = 1; i<= N; i++){ w[i] = sc.nextInt(); value[i] = sc.nextInt(); } int res = getMaxValue(N, w, value, ...
leetcode-1025. 除数博弈
leetcode-1025. 除数博弈
原始思路
1234567891011121314151617181920212223class Solution { public boolean divisorGame(int N) { boolean[] dp = new boolean[N + 1]; if (N == 1) { return false; } if (N == 2) { return true; } if (N == 3) { return false; } dp[1] = false; dp[2] = true; dp[3] = false; for (int i = 4; i <= N; i++) { dp[i] = !dp[i ...
leetcode-518. 零钱兑换 II
leetcode-518. 零钱兑换 II
题解思路
12345678910111213141516171819202122232425class Solution { public int change(int amount, int[] coins) { // 该题有两种状态 使用前i个硬币，第二个是硬币的总额 // 定义dp,dp表示组合数 int[][] dp = new int[coins.length + 1][amount + 1]; //使用0个硬币组合0，是一种组合 for (int i = 0; i <= coins.length ; i++) { dp[i][0] = 1; } //硬币首先看是否能装的下, 装的下的情况又分为可选可不选 for (int i = 1; i <= coins.length; i++) { for (int j ...
leetcode-392. 判断子序列
leetcode-392. 判断子序列
题解思路
1234567891011121314151617181920212223242526272829303132class Solution { public boolean isSubsequence(String s, String t) { int n1 = s.length(); int n2 = t.length(); boolean[][] dp = new boolean[n1 + 1][n2 + 1]; for (int i = 1; i <= n1; i++) { dp[i][0] = false; } for (int i = 0; i <= n2; i++) { dp[0][i] = true; } for (int i = 1; i <= n1; i++) { ...
面试题16.17.连续数列
leetcode面试题 16.17. 连续数列
原始思路
123456789101112131415161718192021class Solution { public int maxSubArray(int[] nums) { int n = nums.length; if (n == 0) { return 0; } int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = nums[i - 1]; } for (int i = 1; i <= n; i++) { dp[i] = Math.max(dp[i], dp[i - 1] + dp[i]); } int res = Integer.MIN_VALUE; ...
leetcode-787K站中转内最便宜的航班
787. K 站中转内最便宜的航班
使用状态转移dp
123456789101112131415161718192021222324class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { //n目的地,最多经过K次中转,说明最多走K + 1 次航班, int[][] dp = new int[n][K + 2]; for (int i = 0; i < n; i++) { for (int j = 0; j < K + 2; j++) { dp[i][j] = 100000000; } } dp[src][0] = 0; for (int i = 1; i <= K + 1; i++) { ...
leetcode-322.零钱兑换
leetcode-322. 零钱兑换
题解思路
12345678910111213141516171819202122class Solution { public int coinChange(int[] coins, int amount) { if (amount <= 0) { return 0; } int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 0; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (coins[j] <= i) { dp[i] = Math.min(dp[i], d ...
leetcode-72编辑距离
leetcode-72. 编辑距离
12345678910111213141516171819202122232425262728class Solution { public int minDistance(String word1, String word2) { int n1 = word1.length(); int n2 = word2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; //初始化行 for (int i = 0; i <= n1; i++) { dp[i][0] = i; } //初始化列 for (int i = 0; i <= n2; i++) { dp[0][i] = i; } for (int i = 1; i <= n1; i++) { ...
leetcode-40.组合总和 II
leetcode-40.组合总和 II
原始思路
123456789101112131415161718192021222324252627282930313233class Solution{ List<List<Integer>> result = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); int total = 0; Set<String> set = new HashSet<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); dfs(0, candidates, target); return result; } publi ...