import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { // write code here if(arr == null || arr.length == 0){ return 0; } //dp[i] 表示 到元素i结尾时，最长的子序列长度，默认是 1 ，当前自己就算一个递增 ...

思路: 1.遍历arr[0, length] , 凑i元钱的种数 == 凑 i - arr[j] 元的种数 + 凑 arr[j] 元的种数 import java.util.*; public class Solution { /** * 最少货币数 * @param arr int整型一维数组 the array * @param aim int整型 the target * @return int整型 */ public int minMoney (int[] arr, int aim) { // write code here //如何使用最少arr元素 构成 aim值 //dp[i] ...

思路: 1.递归思想 2.ABCDEFG，如果D是0,A不是1和2，那么ABCD无法组合，不能出现30 40 这样的组合。如果A是1或2,10 20 是被允许的，那么组合只能是(AB)(CD) 不考虑AB组合的多少。所以利用dp[i] 来代表第i个位置的组合数量，A是1或2 就为 dp[i] = dp[i-2]  3.如果D是1到6，那么如果C是1到2，是不是可以写成(AB)(CD) 或者(ABC)(D) ,公式就是dp[i] = dp[i-2]+dp[i-1],如果C是3到9，那么只能是(ABC)(D) ，dp[i] = dp[i-1] 4.如果D是7到9，那么C是1的话，组合可以是(ABC...

思路: 1.dp[i][j] 到 (i,j)位置的最小路径和 import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here if(matrix == null ){ return 0; } int row = matrix.length; int col = matrix[0].length; //dp[i][j] 代表 到达(...

import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here //dp[j][j] = // + dp[i-1][j] + dp[i][j-1] //dp[i,j]表示到达点(i，j)的路径数 int[][] dp = new int[m][n]; for(int i = 0;i< m;i++){ for(int j = 0;j&...

思路: 1.区别于上一道题，公共子序列，这道题是公共子串 2.利用dp[i][j]记录 str1[0,i-1] 与 str2[0,j-1]的公共子串长度，如果哦str[i-1]== str[j-1]那么 dp[i][j] = dp[i-][j-1] + 1,记录下最大的dp[i][j],再记录此时的下标。遍历结束后，有了公共子串长度和结束位置，不就得出了公共子串么 import java.util.*; public class Solution { /** * longest common substring * @param str1 string字符串 the string * @par...

思路: 1.题目给出目前给出的数据，仅仅会存在一个最长的公共子序列 2.我们利用dp[i][j] 记录 字符串s1的0到i-1位置与字符串s2的0到j-1位置的最长公共子序列长度 3.如果s1.charAt(i-1) == s2.charAt(j-1) ,那么dp[i][j] = dp[i-1][j-1] + 1, 不相等则，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1] 4.我们从字符串后面遍历到前面，如果相等，我们就记录下来，不相等，就看下当前位置[i-1][j]与[i][j-1]的最大公共子序列长度，选择往大的方向偏移，确定最大子序列来自的方向是哪。...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { // write code here //dp[i]表示爬到第i阶梯需要的最小花费 int[] dp = new int[cost.length + 1]; for(int i = 2;i<= cost.length;i++){ ...

public class Solution { //f(1) = 1 f(2) = 2 f{3) = 3 // public int jumpFloor(int target) { return f(target); } public int f(int n){ //公式 f(n) = f(n-1)+f(n-2) if(n <= 0){ return 0; } if(n == 1){ return 1; } if(n == 2){ return 2; } int result = 0; int a = 1; //f(n-2) int b = 2; //f(n-1) for(int i =...

public class Solution { public int Fibonacci(int n) { if (n <= 0) { return 0; } if (n == 1 || n == 2) { return 1; } int a = 1, b = 1; int k = 3; int result = 0; while(k <= n){ result = a + b; a = b; b = result; k ++; } return result; } public int f2(int n) { if (n <= 0 ) { return 0; } if (n...

import java.util.*; public class Solution { //记录四个方向 private int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private int n, m; /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型二维数组 描述矩阵的每个数 * @return int整型 */ public int solve (int[][] matrix) { // write code...

import java.util.*; public class Solution { /** * * @param n int整型 * @return string字符串ArrayList */ public ArrayList<String> generateParenthesis (int n) { // write code here ArrayList<String> result = new ArrayList<String>(); if(n< 1){ return result; } if( n == 1){ result.add("()...

如果皇后出现在第一列，那么第一行的皇后位置就确定了，接下来递归地在剩余的n−1行中找n−1个皇后的位置。 固定一个[i,j]，那接下来的第j+1列，尝试选择n种位置，每一行都递归尝试，反之亦然，但是在每次尝试j+1列，不同行的位置时，是不是要将这一列都清空。 import java.util.*; public class Solution { /** * * @param n int整型 the n * @return int整型 */ public int Nqueen (int n) { // write code here if(n <= 0){ return 0; } if(n...

思路: 两种方法 1.起始位置有n种选择，所以每次更换i位置和起始位置的值，然后再递归 2.起始位置固定，例如第1个数，固定，剩下的有 n - 1 种可能，然后递归，回溯 import java.util.*; public class Solution { public ArrayList<String> Permutation(String str) { if(str == null){ return null; } ArrayList<String> result = new ArrayList<>(); permutationHelper(str.t...