public int fib(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
return fib(n-1)+fib(n-2);
}- 粗略地测试算法执行时间：
@Test
public void test(){
//int n=10; //time:2.0921E-5s
//int n=20; //time:0.009386947s
//int n=30; //time:0.049079365s
//int n=40;//time:1.157836107s
int n=42; //time:2.560889825s
//可以看到时间是成指数级增长的
long startTime=System.nanoTime();
int res=fib(n);s
long endTime=System.nanoTime();
System.out.println("fib("+n+")="+res);
System.out.println("time:"+(endTime-startTime)/1000000000.0+"s");
}时间是成指数级增长的，这是非常可怕的，原因：存在大量的重复计算（途中粉色部分）：
- 使用记忆化搜索进行优化：
//改进上面的方法：采用记忆化搜索
private int[] memo;
public int fib2(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
if(memo[n]==-1){
//memo[n]==-1说明是首次计算，下一次遇到该值就直接返回了
memo[n]=fib2(n-1)+fib2(n-2);
}
return memo[n];
}- 此时，再粗略地测试算法执行时间：
@Test
public void test2(){
//int n=10; //time:7.106E-6s
//int n=20; //time:8.289E-6s
//int n=30; //time:2.0132E-5s
//int n=40;//time:1.2632E-5s
int n=42; //time:1.1843E-5s
//为memo分配空间，并且初始值设为-1,因为斐波那契数列中是没有-1的
memo=new int[n+1];
for(int i=0;i<n+1;i++){
memo[i]=-1;
}
long startTime=System.nanoTime();
int res=fib2(n);
long endTime=System.nanoTime();
System.out.println("fib2("+n+")="+res);
System.out.println("time:"+(endTime-startTime)/1000000000.0+"s");
}动态规划就是将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
//思路一：递归
//分析（自顶向下）：
private int calcWays(int n){
if(n==1){
return 1;
}
if(n==2){
return 2;
}
return calcWays(n-1)+calcWays(n-2);
}
public int climbStairs(int n) {
return calcWays(n);
}显然存在大量重复计算的，如下图：
- 使用记忆化搜索进行改进:
private int[] memo;
private int calcWays(int n){
if(n==1){
return 1;
}
if(n==2){
return 2;
}
if(memo[n]==-1){
memo[n]=calcWays(n-1)+calcWays(n-2);
}
return memo[n];
}
public int climbStairs(int n) {
memo=new int[n+1];
for(int i=0;i<n+1;i++){
memo[i]=-1;
}
return calcWays(n);
}//思路二：
public int climbStairs(int n) {
int[] memo=new int[n+1];
if(n<=1){
return 1;
}
memo[1]=1;
//注意：这里 小标是2,说明数组长度至少为3,n至少为2，所以前面要对n进行判断
memo[2]=2;
for(int i=3;i<=n;i++){
memo[i]=memo[i-1]+memo[i-2];
}
return memo[n];
}
@Test
public void test(){
int n=2;
//int n=3;
System.out.println(climbStairs(n));
}//思路：f(i,j) 考虑从第一个元素到i行j列的最小路径和。
// 状态转移方程：
// f(0,0)=tri[0][0]
// f(i,0)=tri[i][0]+f(i-1,0) (i>0)
// f(i,i)=tri[i][i]+f(i-1,i-1)(i>=1)
// f(i,j)=tri[i][j]+min{f(i-1,j-1),f(i-1,j)}
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==0){
return 0;
}
//该三角形总共有 n 层
int n = triangle.size();
int[][] dp = new int[n][];
for(int i=0;i<n;i++){
dp[i] = new int[i+1];
}
dp[0][0] = triangle.get(0).get(0);
for(int i=1;i<n;i++){
dp[i][0]=triangle.get(i).get(0)+dp[i-1][0];
dp[i][i]=triangle.get(i).get(i)+dp[i-1][i-1];
for(int j=1;j<i;j++){
dp[i][j]=triangle.get(i).get(j)+
Math.min(dp[i-1][j-1],dp[i-1][j]);
}
}
Arrays.sort(dp[n-1]);
return dp[n-1][0];
}
@Test
public void test(){
List<Integer> l1= Arrays.asList(2);
List<Integer> l2= Arrays.asList(3,4);
List<Integer> l3= Arrays.asList(6,5,7);
List<Integer> l4= Arrays.asList(4,1,8,3);
List<List<Integer>> triangle = new ArrayList<>();
triangle.add(l1);
triangle.add(l2);
triangle.add(l3);
triangle.add(l4);
System.out.println(minimumTotal(triangle));
}//改进：
//可以使用一维数组改进。
//从最后一行开始，不断更新数组 f(i) 考虑从最后一行到第 i 行、第 j 列的最小路径和。
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==0){
return 0;
}
//该三角形总共有 n 层
int n = triangle.size();
int[] dp = new int[n];
for(int i=n-1;i>=0;i--){
for(int j=0;j<=i;j++){
if(i==n-1){
//实际上是初始化该数组
dp[j] = triangle.get(i).get(j);
}else{
dp[j] = triangle.get(i).get(j) + Math.min(dp[j],dp[j+1]);
}
}
}
return dp[0];
}
@Test
public void test(){
List<Integer> l1= Arrays.asList(2);
List<Integer> l2= Arrays.asList(3,4);
List<Integer> l3= Arrays.asList(6,5,7);
List<Integer> l4= Arrays.asList(4,1,8,3);
List<List<Integer>> triangle = new ArrayList<>();
triangle.add(l1);
triangle.add(l2);
triangle.add(l3);
triangle.add(l4);
System.out.println(minimumTotal(triangle));
}public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
if(numRows<=0){
return res;
}
for(int i=0;i<numRows;i++){
List<Integer> list = new ArrayList<>();
for(int j=0;j<i+1;j++){
if(j==0 || i==j){
//已处理了 i =0 的情况，所以下面不用担心 i-1 < 0 的情况
list.add(1);
}else {
list.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
}
res.add(list);
}
return res;
}
@Test
public void test(){
int numRows = 5;
List<List<Integer>> res = generate(numRows);
for(List<Integer> list : res){
System.out.println(list);
}
}public int rob(int[] nums) {
int n = nums.length;
if(n == 1){
return nums[0];
}
if(n == 2){
return Math.max(nums[0],nums[1]);
}
//dp[i] 表示偷窃到第 i 间房子，获取的最高金额。
int[] dp =new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<n;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
}
@Test
public void test(){
//int[] nums = {1,2,3,1};
int[] nums = {2,7,9,3,1};
System.out.println(rob(nums));
}//对上述的空间复杂度进行优化
public int rob(int[] nums) {
int n = nums.length;
if(n == 1){
return nums[0];
}
if(n == 2){
return Math.max(nums[0],nums[1]);
}
int pre1 = nums[0];
int pre2 = Math.max(nums[0],nums[1]); // pre2 是这两个元素的较大值
for(int i=2;i<n;i++){
int cur = Math.max(pre1 + nums[i],pre2);
pre1 = pre2;
pre2 = cur;
}
return pre2;
}
@Test
public void test(){
int[] nums = {1,2,3,1};
//int[] nums = {2,7,9,3,1};
System.out.println(rob(nums));
}public int rob(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
return Math.max(tryRob(nums,0, nums.length-2),
tryRob(nums,1,nums.length-1));
}
private int tryRob(int[] nums,int start,int end){
if(start == end){
return nums[start];
}
int pre1 = nums[start];
int pre2 = Math.max(nums[start],nums[start+1]);
for(int i=start+2;i<=end;i++){
int cur = Math.max(pre1+nums[i],pre2);
pre1 = pre2;
pre2 = cur;
}
return pre2;
}
@Test
public void test(){
//int[] nums = {2,3,2};
int[] nums = {1,2,3,1};
System.out.println(rob(nums));
}//思路：
//思路一：递归 + 记忆化素搜索的方式
private int[] memo;
// 分割整数 n，返回最大乘积
private int breakInteger(int n){
if(n==1){
return 1;
}
if(n==2){
return 1;
}
if(memo[n]!=-1){
return memo[n];
}
int res = 1;
for(int i=1;i<n;i++){
res = max3(res,i*(n-i),i*breakInteger(n-i));
}
memo[n] = res;
return res;
}
private int max3(int a,int b,int c){
int tmp = a>b?a:b;
return (tmp>c)?tmp:c;
}
public int integerBreak(int n) {
memo = new int[n+1];
for(int i=0;i<n+1;i++){
memo[i] = -1;
}
return breakInteger(n);
}
@Test
public void test(){
//int n=2;
int n=10;
System.out.println(integerBreak(n));
}//思路二：动态规划
private int max3(int a,int b,int c){
int tmp = a>b?a:b;
return (tmp>c)?tmp:c;
}
public int integerBreak(int n) {
if(n==1){
return 1;
}
if(n==2){
return 1;
}
//dp[i] 表示将 i 拆分后得到的最大乘积
int[] dp = new int[n+1];
dp[1] = 1;
for(int i=2;i<n+1;i++){
for(int j=1;j<i;j++){
dp[i] = max3(dp[i],j*(i-j),j*dp[i-j]);
}
}
return dp[n];
}
@Test
public void test(){
//int n=2;
int n=10;
System.out.println(integerBreak(n));
}//思路：类似 343 题
public int numSquares(int n) {
if(n==1 || n==2){
return n;
}
//dp[i] 表示将 i 拆分为若干个完全平方数之和的完全平方数的最少个数。
int[] dp = new int[n+1];
for(int i=0;i<n+1;i++){
dp[i]=Integer.MAX_VALUE;
}
dp[0] = 0;
for(int i=1;i<n+1;i++){
for(int j=1;j*j<=i;j++){
//<= ?
//比如 i=1，j=1,此时 j*j<=i 。即 n=1=1 (第一个1是 n 值，第二个1是完全欧英防暑) 是成立的
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
@Test
public void test(){
//int n=12;
int n=13;
System.out.println(numSquares(n));
}public int numDecodings(String s) {
if(s==null || s.length()==0){
return 0;
}
int n=s.length();
//dp[i] 记录的是 s.substring(0,i) 的解码方法总数
int[] dp=new int[n+1];
dp[0] = 1;
if(s.charAt(0)>'0'){
//如果第一位上是0，那么无法转码,dp[1]=0,否则dp[1]=1
dp[1]=1;
}
for(int i=2;i<=n;i++){
if(s.charAt(i-1)>='1'){
//查看 i 位置的前 1 位元素是否可转码，则到 i 位置解码方法总数不变
dp[i] = dp[i-1];
}
int num = Integer.parseInt(s.substring(i-2,i));
if(num>= 10 && num <=26){
dp[i] = dp[i] + dp[i-2];
}
}
return dp[n];
}
@Test
public void test(){
String s="12";
//String s="226";
System.out.println(numDecodings(s));
}- 问题描述：
有一个背包，它的容量为 C。现在有 n 种不同的物品，编号为 0...n-1，其中每一件物品的重量为 w(i)，价值为v(i)。 问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，包中物品的总价值最大。
-
思路一：使用贪心策略解决，即优先放入单位重量价值最高的物品。
假设有一个容量为 5 的背包。相关物品的重量和价值如下表：
id 0 1 2 weight 1 2 3 value 6 10 12 value / weight 6 5 4 按照上述的贪心策略，将物品 0 和物品 1 放入包中，此时包中的物品总价值为 16。如果将物品 1 和物品 2 放入包中，包中的物品总价值为 22。
显然，上述贪心策略不能解决 0-1 背包问题。
-
思路二：递归+记忆化搜索：
F(n,C) 考虑将 n 个物品放进容量为 C 的背包，使得价值最大
则对于 F(i,C) 有两种情况：
(1)不将 i 物品放入：
F(i,C)=F(i-1,C)(2)将 i 物品放入：
F(i,C)=v(i)+F(i-1,C-w(i))综合上述两种情况：
F(i,C)=max{F(i-1,C),v(i)+F(i-1,C-w(i))}//写法一：使用递归来求解决该问题 --> 但是复杂度太高了 //用 [0...index] 的物品，填充到容量为 C 的背包中的最大价值 private int bestValue(int[] v,int[] w,int C,int index){ if(index<0 || C<=0){ return 0; } //(1)不将 index 物品放入 int res = bestValue(v,w,C,index-1); //(2)将 index 物品放入，需要先判断该物品能否被装下 if(C>=w[index]){ res=Math.max(res,v[index]+bestValue(v,w,C-w[index],index-1)); } return res; } public int knapsack01(int[] v,int[] w,int C){ int n = w.length; return bestValue(v,w,C,n-1); } @Test public void test(){ //int[] v={6,10,12}; //int[] w={1,2,3}; //int C= 5; //22 int[] v={3,4,5,8,10}; int[] w={2,3,4,5,9}; int C=20; System.out.println(knapsack01(v,w,C)); //26 }
//写法二：使用记忆化搜索的方式来改进上述写法 private int[][] memo; //记忆化搜索的数组，初始化值全为-1 //用 [0...index] 的物品，填充到容量为 C 的背包中的最大价值 private int bestValue(int[] v,int[] w,int C,int index){ if(index<0 || C<=0){ return 0; } if(memo[index][C]!=-1){ return memo[index][C]; } //(1)不将 index 物品放入 int res = bestValue(v,w,C,index-1); //(2)将 index 物品放入，需要先判断该物品能否被装下 if(C>=w[index]){ res=Math.max(res,v[index]+bestValue(v,w,C-w[index],index-1)); } memo[index][C] = res; return res; } public int knapsack01(int[] v,int[] w,int C){ int n = w.length; memo = new int[n][C+1]; //声明 n 行(C+1）列的二维数组。因为物品编号在[0...n-1],包的容量为C。 for(int i=0;i<n;i++){ Arrays.fill(memo[i],-1); } return bestValue(v,w,C,n-1); } @Test public void test(){ int[] v={6,10,12}; int[] w={1,2,3}; int C= 5; //22 //int[] v={3,4,5,8,10}; //int[] w={2,3,4,5,9}; //int C=20; System.out.println(knapsack01(v,w,C)); //26 }
-
思路三：动态规划方式：
dp[i][j]表示用 [0...i] 的物品，填充到容量为 j 的背包中的最大价值。则对与第 i 个物品有:(1) 不放入该背包中：
dp[i][j]=dp[i-1][j](2)放入该背包中：判断此时背包容量是否能够放入该 i 物品即 j >= w[i]。若能够放下。则有：
dp[i][j]=v[i]+dp[i-1][j-w[i]]综合(1)(2)，
dp[i][j]=Math.max(dp[i-1][j],dp[i][j]=v[i]+dp[i-1][j-w[i]])public int knapsack01(int[] v,int[] w,int C){ int n = w.length; //dp[i][j] 用[1...i]物品来填充容量为 j 的背包的最大价值 int[][] dp = new int[n+1][C+1]; for(int i=0;i<=n;i++){ dp[i][0] = 0; } for(int j=0;j<=C;j++){ dp[0][j] = 0; } for(int i=1;i<=n;i++){ for(int j=0;j<=C;j++){ //对于第 i 个物品有: //(1) 不放入该背包中：`dp[i][j]=dp[i-1][j]` //(2)放入该背包中：判断此时背包容量是否能够放入该 i 物品即 j >= w[i-1]。 // 若能够放下。则有:dp[i][j]=v[i-1]+dp[i-1][j-w[i-1]] //TODO:注意数组下标，在数组 w 和 v 中，第 i 个物品的下标是 (i-1) dp[i][j] = dp[i-1][j]; if(j>=w[i-1]){ dp[i][j] =Math.max(dp[i][j],v[i-1]+dp[i-1][j-w[i-1]]); } } } return dp[n][C]; } @Test public void test(){ //int[] v={6,10,12}; //int[] w={1,2,3}; //int C= 5; //22 int[] v={3,4,5,8,10}; int[] w={2,3,4,5,9}; int C=20; System.out.println(knapsack01(v,w,C)); //26 }
求出具体解：
// bag[i] = 1 表示将第 i 个物品放入包中； // bag[i] = 0 表示未将第 i 个物品被放入包中； private int[] bag; public void knapsack01(int[] v,int[] w,int C){ int n = w.length; //dp[i][j] 用[1...i]物品来填充容量为 j 的背包的最大价值 int[][] dp = new int[n+1][C+1]; for(int i=0;i<=n;i++){ dp[i][0]=0; } for(int j=0;j<=C;j++){ dp[0][j]=0; } for(int i=1;i<=n;i++){ for(int j=0;j<=C;j++){ //对于第 i 个物品有: //(1) 不放入该背包中：`dp[i][j]=dp[i-1][j]` //(2)放入该背包中：判断此时背包容量是否能够放入该 i 物品即 j >= w[i-1]。 // 若能够放下。则有:dp[i][j]=v[i-1]+dp[i-1][j-w[i-1]] //TODO:注意数组下标，在数组 w 和 v 中，第 i 个物品的下标是 (i-1) dp[i][j] = dp[i-1][j]; if(j>=w[i-1]){ dp[i][j] =Math.max(dp[i][j],v[i-1]+dp[i-1][j-w[i-1]]); } } } System.out.println("max value: "+dp[n][C]); //求出具体将那些物品放入包中 for(int i=n;i>0;i--){ if(dp[i][C] > dp[i-1][C]){ //可以将第 i 个物品放入包中 bag[i]=1; C-=w[i-1]; //注意下标：这里的第 i 物品的下标是 (i-1)，容量 C 也发生了变化 }else{ bag[i]=0; } } } @Test public void test(){ //int[] v={6,10,12}; //int[] w={1,2,3}; //int C= 5; //22 int[] v={3,4,5,8,10}; int[] w={2,3,4,5,9}; int C=20; bag = new int[v.length+1]; knapsack01(v,w,C); //26 for(int i=1;<bag.length;i++){ System.out.println(bag[i]); } }
上面的 0-1 背包问题：
-
时间复杂度 O(n*C)
-
空间复杂度 O(n*C)
其中，n 是物品数量，C 是背包容量。
这里针对空间复杂度进行优化：
- 方案一：
对于公式 F(i,C)=max{F(i-1,C),v(i)+F(i-1,C-w(i))} ：
第 i 行元素，依赖于 (i-1) 行元素，可以将空间复杂度就变成 O(2*C)=O(C)
public int knapsack01(int[] v,int[] w,int C){
int n = w.length;
int[][] dp = new int[2][C+1];
for(int i=0;i<2;i++){
dp[i][0]=0;
}
for(int j=0;j<=C;j++){
dp[0][j]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=C;j++){
//对于第 i 个物品有:
//(1) 不放入该背包中：`dp[i][j]=dp[i-1][j]`
//(2)放入该背包中：判断此时背包容量是否能够放入该 i 物品即 j >= w[i-1]。
// 若能够放下。则有:dp[i][j]=v[i-1]+dp[i-1][j-w[i-1]]
//TODO:注意数组下标，在数组 w 和 v 中，第 i 个物品的下标是 (i-1)
dp[i%2][j] = dp[(i-1)%2][j];
if(j>=w[i-1]){
dp[i%2][j] =Math.max(dp[i%2][j],v[i-1]+dp[(i-1)%2][j-w[i-1]]);
}
}
}
return dp[n%2][C];
}
@Test
public void test(){
int[] v={6,10,12};
int[] w={1,2,3};
int C= 5; //22
//int[] v={3,4,5,8,10};
//int[] w={2,3,4,5,9};
//int C=20;
System.out.println(knapsack01(v,w,C));
}- 方案二：
观察下图，可以看出F(i,C) 实际上就是 F(i,C)的值与 v(i)+F(i,C-w(i))的值取最大值的问题。
从后向前遍历，空间复杂度就变成 O(C)。
public int knapsack01(int[] v,int[] w,int C){
int n = w.length;
//dp[j] 表示 n 物品中选择放到容量为 C 的物品的最大价值。
int[] dp = new int[C+1];
for(int i=1;i<=n;i++){
for(int j=C;j>=w[i-1];j--){
dp[j] = Math.max(dp[j],v[i-1]+dp[j-w[i-1]]);
}
}
return dp[C];
}
@Test
public void test(){
// int[] v={6,10,12};
// int[] w={1,2,3};
// int C= 5; //22
int[] v={3,4,5,8,10};
int[] w={2,3,4,5,9};
int C=20;
System.out.println(knapsack01(v,w,C)); //26
}//思路：实际上是 0-1 背包问题的变形。
//F(n,C) 考虑 n 个物品填满容量为 C 的背包。
//(1)不选取 i 个物品: F(i-1,C)
//(2)选取 i 个物品: F(i-1,c-w[i])
//时间复杂度：O(n*sum/2)=O(n*sum)（其中 n是数组长度）
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
if(sum%2==1){ //要使两个子集的元素和相等，则数组中的元素和必定是偶数。
return false;
}
int C = sum/2;
// dp[i] 表示是否可以选取数组中的元素放入容量为 i 的背包中，使得包能恰好装满
boolean[] dp = new boolean[C+1];
//数组中第 0 个元素是否可以放入
for(int j=0;j<=C;j++){
dp[j] = (j==nums[0]);
//可以将数组的第一个元素，放入容量为 nums[0] 的背包中
}
for(int i=1;i< nums.length;i++){
//注意这里 i 的下标是从1开始的，之前已经考虑了第 0 个元素
for(int j=C;j>=nums[i];j--){
dp[j] = (dp[j] || dp[j-nums[i]]);
}
}
return dp[C];
}
@Test
public void test(){
//int[] nums={1,5,11,5};
//int[] nums={1,2,3,5};
int[] nums={1,2,5};
System.out.println(canPartition(nums));
}//思路：
//假设原数组为nums，目标值为S，那么原数组必然可以分成两个部分：
//一个部分里面的元素前面需要加"-"，即运算的时候应该是做减法;
//另一个部分里面的元素前面需要加"+"，即运算的时候应该是做加法。
//我们将做加法部分的数组记为 P，做减法部分的数组记为 N。
//举个例子，例如 nums = {1，2，3，4，5}，S = 3。
//那么有一种可以是1-2+3-4+5，即 P = {1，3，5}，N = {2，4}；
//于是我们可以知道：S = sum(P) - sum(N)
//又因为 sum(nums)= sum(P)+sum(N)
//所以 sum(nums)+S = 2*sum(P)
//sum(P) = [S + sum(nums)] / 2 ([]表示向下取整)
//那么就转换为动态规划问题。
//可以参考 416 题。
public int findTargetSumWays(int[] nums, int S) {
int n =nums.length;
int sum=0;
for(int i=0;i<n;i++){
sum += nums[i];
}
if(sum < S || (S+sum)%2!=0){
//注意 S+sum 必然是偶数
return 0;
}
int C=(S+sum)/2;
int[] dp=new int[C+1];
dp[0]=1;
for(int i=0;i<nums.length;i++){
for(int j=C;j>=nums[i];j--){
dp[j] = dp[j] + dp[j-nums[i]];
}
}
return dp[C];
}
@Test
public void test(){
int[] nums={1, 1, 1, 1, 1};
int S=3;
System.out.println(findTargetSumWays(nums,S));
}//思路：实际上是 0-1 背包问题的变种,即完全背包问题。
//每个物品可以无限使用
public int combinationSum4(int[] nums, int target) {
if(nums==null || nums.length==0 || target<=0){
return 0;
}
//dp[i] 表示和为 i 的组合的个数
int[] dp=new int[target+1];
dp[0] = 1;
//完全背包问题
for(int i=1;i<=target;i++){
for(int j=0;j<nums.length;j++){
if(i>=nums[j]){
dp[i] = dp[i] + dp[i-nums[j]];
}
}
}
return dp[target];
}
@Test
public void test(){
int[] nums={1,2,3};
int target = 4;
System.out.println(combinationSum4(nums,target));
}//思路：因为硬币可以重复使用，因此这是一个完全背包问题。
//完全背包只需要将 0-1 背包中逆序遍历 dp 数组改为正序遍历即可。
public int coinChange(int[] coins, int amount) {
//dp[i] 以凑成总金额为 i 所需的最少的硬币个数
//dp[i]=min{dp[i],dp[i-coin]+1}
int[] dp=new int[amount+1];
dp[0] =0;
//dp 数组初始值只要大于 amount 即可（coin 面值为1，最多为 amount）
for(int i=1;i<=amount;i++){
dp[i] = amount+1;
}
for(int coin:coins){
for(int i=coin;i<=amount;i++){
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
return (dp[amount]==amount+1)?-1:dp[amount];
}
@Test
public void test(){
int[] coins={1,2,5};
int amount=11;
System.out.println(coinChange(coins,amount));
}//思路：完全背包问题
public int change(int amount, int[] coins) {
//dp[i] 表示凑成总金额为 i 的硬币组合数
int[] dp=new int[amount+1];
dp[0]=1;
for(int coin:coins){
for(int j=coin;j<=amount;j++){
dp[j] = dp[j] + dp[j-coin];
}
}
return dp[amount];
}
@Test
public void test(){
//int[] coins={1,2,5};
//int amount=5;
//int[] coins={2};
//int amount=3;
int[] coins={10};
int amount=10;
System.out.println(change(amount,coins));
}//思路：0-1 背包问题的变形
//1和0的数量相当于背包容量。
//memo[i][j]表示 0 的个数为 i，1 的个数为 j 能拼出字符串的最大数量。
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
for(String str:strs){
char[] chs=str.toCharArray();
int cnt0=0;//统计 str 中 '0' 出现次数
int cnt1=0;//统计 str 中 '1' 出现次数
for(int i=0;i<chs.length;i++){
if(chs[i]=='0'){
cnt0++;
}
if(chs[i]=='1'){
cnt1++;
}
}
//类似 0-1 背包问题从后向前遍历
for(int i=m;i>=cnt0;i--){
for(int j=n;j>=cnt1;j--){
dp[i][j] = Math.max(dp[i][j],dp[i-cnt0][j-cnt1]+1);
}
}
}
return dp[m][n];
}/**
* 思路：
* dp[i]表示字符串s[0...i)能否拆分成符合要求的子字符串。
* 我们可以看出，如果s[j...i)在给定的字符串组中，且dp[j]为True（即字符串s[0...j)能够拆分成符合要求的子字符串），那么此时dp[i]也就为True了。
* 状态转移方程：
* dp[0]=true;
* dp[i]=dp[j] && DICT（s[j...i)）,0<=j<i
*/
public boolean wordBreak(String s, List<String> wordDict) {
int n=s.length();
boolean[] memo=new boolean[n+1];
memo[0]=true;
for (int i = 1; i <= n; i++){
for (int j = 0; j < i; j++) {
// 注意substring是前闭后开
String tmp = s.substring(j, i);
if (memo[j] && wordDict.contains(tmp)) {
memo[i] = true;
break;
}
}
}
return memo[n];
}public int rob(TreeNode root) {
return rob(root,true);
}
private int rob(TreeNode root,boolean include){
if(root==null){
return 0;
}
int res=rob(root.left,true)+rob(root.right,true);
if(include){
res=Math.max(res,root.val+rob(root.left,false)+rob(root.right,false));
}
return res;
}public int rob(TreeNode root) {
int[] res=tryRob(root);
return Math.max(res[0],res[1]);
}
private int[] tryRob(TreeNode root){
if(root==null){
return new int[]{0,0};
}
int[] resultL=tryRob(root.left);
int[] resultR=tryRob(root.right);
int[] res=new int[2];
//小标0 表示不抢劫该根节点的最大价值，小标1表示抢劫该根节点的最大价值
//不抢劫该根节点
res[0]=resultL[1]+resultR[1];
res[1]=Math.max(res[0],root.val+resultL[0]+resultR[0]);
return res;
}class NumArray {
private int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int n = A.length;
int[] dp = new int[n];
for (int i = 2; i < n; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
}
}
int total = 0;
for (int cnt : dp) {
total += cnt;
}
return total;
}/**
* 思路：
* LIS(i):表示以第i个数字为结尾的最长上升子序列的长度，
* 即在[0...i]范围内,选择数字nums[i]可以获得的最长子序列的长度。
* LIS(i)=max(j<i){1+LCS(j) if(nums[i]>nums[j])}
*/
public int lengthOfLIS(int[] nums) {
int n=nums.length;
if(n==0){
return 0;
}
int[] memo=new int[n];
for(int i=0;i<n;i++){
memo[i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
memo[i]=Math.max(memo[i],1+memo[j]);
}
}
}
int res=1;
for(int i=0;i<n;i++){
res=Math.max(res,memo[i]);
}
return res;
}//用up[i]和down[i]分别记录到第i个元素为止 以上升沿和下降沿[结束] 的最长“摆动”序列长度
public int wiggleMaxLength(int[] nums) {
int n=nums.length;
if(n==0 || n==1){
return n;
}
int[] up=new int[n];
int[] down=new int[n];
up[0]=1;
down[0]=1;
for(int i=1;i<n;i++){
if(nums[i]>nums[i-1]){ //下降
down[i]=up[i-1]+1;
up[i]=up[i-1];
}else if(nums[i]<nums[i-1]){
up[i]=down[i-1]+1;
down[i]=down[i-1];
}else{
up[i]=up[i-1];
down[i]=down[i-1];
}
}
return Math.max(up[n-1],down[n-1]);
}优化：
public int wiggleMaxLength(int[] nums) {
int n=nums.length;
if(n==0 || n==1){
return n;
}
int up=1;
int down=1;
for(int i=1;i<n;i++){
if(nums[i]>nums[i-1]){
down=up+1;
}
if(nums[i]<nums[i-1]){
up=down+1;
}
}
return Math.max(down,up);
}/**
* 思路：
* LIS问题的变种：
* LIS(i):表示以第i个数字为结尾的最长上升子序列的长度， 即在[0...i]范围内, 选择数字nums[i]可以获得的最长子序列的长度。
* LIS(i)=max(j<i){1+LCS(j) if(nums[i]>nums[j])}
* 这里要求统计 最长上升子序列的数目
*
* count[i]在[0...i]范围内的最长子序列的个数
*/
public int findNumberOfLIS(int[] nums) {
int n=nums.length;
if(n==0){
return 0;
}
int[] memo=new int[n];
int[] count=new int[n];
int maxlen=1;
for(int i=0;i<n;i++){
memo[i]=1;
count[i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
if(memo[j]+1>memo[i]){
//说明这个长度的序列是新出现
memo[i]=1+memo[j];
count[i]=count[j];
}else if(memo[j]+1==memo[i]){
count[i]+=count[j];
}
}
}
maxlen=Math.max(maxlen,memo[i]);
}
int res=0;
for(int i=0;i<n;i++){
if(memo[i]==maxlen){
res+=count[i];
}
}
return res;
}- 问题：
给出两个字符串S1和S2，求这两个字符串的最长公共子序列
- 示例：
s1=ABCD,s2=AEBD
最长公共子序列为[ABD]
- 解题：
状态： LCS(m,n) S1[0...m]和S2[0...n]的最长公共子序列
状态转移方程： 当S1[m]==S2[n]时
LCS(m,n)=1+LCS(m-1,n-1);
当S1[m]!=S2[n]时
LCS(m,n)=max{LCS(m,n-1),LCS(m-1,n)}
public int LCS(String s,String t){
int m=s.length();
int n=t.length();
if(m==0 || n==0){
return 0;
}
int[][] lcs=new int[m+1][n+1];
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
lcs[i][j]=0;
}
}
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(s.charAt(i-1)==t.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
}else{
lcs[i][j]=Math.max(lcs[i-1][j],lcs[i][j-1]);
}
}
}
return lcs[m][n];
}LCS的具体解：
public class LCSSolution {
//记录最长公共子序列的走向 'c'表示斜方向 ‘l’表示左方向 ‘u’表示上方向
char[][] x;
public int LCSLength(String s,String t,int m,int n){
if(m==0 || n==0){
return 0;
}
int[][] lcs=new int[m+1][n+1];
x=new char[m+1][n+1];
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
lcs[i][j]=0;
}
}
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
//注意：这里的i是从1开始的 i=m时，实际上取到的是s的第m个元素
if(s.charAt(i-1)==t.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
x[i][j]='c';
}else if(lcs[i-1][j]>=lcs[i][j-1]){
lcs[i][j]=lcs[i-1][j];
x[i][j]='u';
}else if(lcs[i-1][j]<lcs[i][j-1]){
lcs[i][j]=lcs[i][j-1];
x[i][j]='l';
}
}
}
return lcs[m][n];
}
public void printLCS(String s,int m,int n){
if(m==0 || n==0){
return;
}
if(x[m][n]=='c'){
printLCS(s,m-1,n-1);
System.out.print(s.charAt(m-1));
}else if(x[m][n]=='u'){
printLCS(s,m-1,n);
}else if(x[m][n]=='l'){
printLCS(s,m,n-1);
}
}
@Test
public void test(){
String s="abcfbc";
String t="abfcab";
int m=s.length();
int n=t.length();
//String s="a";
//String t="ab";
LCSLength(s,t,m,n);
printLCS(s,m,n);
}
}/**
* 思路：
* 要想获得最少步骤,只需要将这两个字符串通过一定步骤转化他们的最长公共子序列即可。
* 由于1次步骤只能删除一个字符，则最少步骤就是
* 两字符串长度和-2*最长公共子序列长度
*/
public int minDistance(String word1, String word2) {
int m=word1.length();
int n=word2.length();
if(m==0){
return n;
}
if(n==0){
return m;
}
int[][] lcs=new int[m+1][n+1];
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
lcs[i][j]=0;
}
}
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
lcs[i][j]=1+lcs[i-1][j-1];
}else{
lcs[i][j]=Math.max(lcs[i-1][j],lcs[i][j-1]);
}
}
}
return (m+n-2*lcs[m][n]);
}//思路：dp[i][j] 表示到 grid[i][j] 的最短路径
// dp[i][j] = min {dp[i-1][j],dp[i][j-1]} + grid[i][j]
//时间复杂度 O(m*n)
//空间复杂度 O(m*n)
public int minPathSum(int[][] grid) {
int m = grid.length;
if(m==1){ //保证了后面的 grid 至少 2 行
//只有一行，则只能一直向右行走
return getSum(grid[0]);
}
int n = grid[0].length;
// dp[i][j] 表示到 grid[i][j] 的最短路径
int[][] dp =new int[m][n];
dp[0][0] =grid[0][0];
//一路向右走
for(int j=1;j<n;j++){
dp[0][j] = grid[0][j] + dp[0][j-1];
}
//一路向下走
/*for(int i=1;i<m;i++){
dp[i][0] = grid[i][0] + dp[i-1][0];
}*/
for(int i=1;i<m;i++){
dp[i][0] = grid[i][0] + dp[i-1][0];
for(int j=1;j<n;j++){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
private int getSum(int[] nums){
int sum=0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
}
return sum;
}
@Test
public void test(){
int[][] gird={
{1,3,1},
{1,5,1},
{4,2,1}
};
System.out.println(minPathSum(gird));
}//优化:
//优化空间复杂度：O(n)
public int minPathSum(int[][] grid) {
int m = grid.length;
if(m==1){ //保证了后面的 grid 至少 2 行
//只有一行，则只能一直向右行走
return getSum(grid[0]);
}
int n = grid[0].length;
int[][] dp = new int[2][n];
dp[0][0] =grid[0][0];
for(int j=1;j<n;j++){
dp[0][j]=dp[0][j-1]+grid[0][j];
}
dp[1][0] = grid[1][0] + dp[0][0];
//上述对第1行进行初始化，对第2行的第一个元素赋值
for(int i=1;i<m;i++){
dp[i%2][0] = grid[i][0] + dp[(i-1)%2][0];
for(int j=1;j<n;j++){
dp[i%2][j] = grid[i][j] + Math.min(dp[(i-1)%2][j],dp[i%2][j-1]);
}
}
return dp[(m-1)%2][n-1];
}
private int getSum(int[] nums){
int sum=0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
}
return sum;
}//思路一：动态规划
public int uniquePaths(int m, int n) {
if(m<=0){
return 0;
}
if(m==1 || n==1){ //只有一条路径可以走
return 1;
}
//dp[i][j] 表示从 (0,0) -> (i,j) 的路径数
int[][] dp = new int[m][n];
for(int j=0;j<n;j++){
dp[0][j]=1;
}
for(int i=0;i<m;i++){
dp[i][0]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
@Test
public void test(){
//int m=3;
//int n=2;
int m=7;
int n=3;
System.out.println(uniquePaths(m,n));
}//对思路一进行空间优化
public int uniquePaths(int m, int n) {
if(m<=0){
return 0;
}
if(m==1 || n==1){ //只有一条路径可以走
return 1;
}
int[] dp = new int[n];
for(int j=0;j<n;j++){
dp[j]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[j] = dp[j] + dp[j-1];
}
}
return dp[n-1];
}
@Test
public void test(){
//int m=3;
//int n=2;
int m=7;
int n=3;
System.out.println(uniquePaths(m,n));
}//思路二：
// 直接用数学公式求解，这是一个组合问题。机器人总共移动的次数 S=m+n-2，向下移动的次数 D=m-1，
// 那么问题可以看成从 S 中取出 D 个位置的组合数量，这个问题的解为 C(S, D)。
public int uniquePaths(int m, int n) {
if(m<=0){
return 0;
}
if(m==1 || n==1){ //只有一条路径可以走
return 1;
}
int S = m+n-2;
int D = m-1;
long res = 1;
for(int i=1;i<=D;i++){
res = res*(S-D+i) / i;
}
return (int)res;
}
@Test
public void test(){
int m=3;
int n=2;
//int m=7;
//int n=3;
System.out.println(uniquePaths(m,n));
}//思路：其实与 62 题类似
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
if(m==0){
return 0;
}
int n=obstacleGrid[0].length;
if(obstacleGrid[0][0]==1){ //这里要特点注意，起始点有障碍物，则无法到达终点
return 0;
}
//dp[i][j] 表示（0,0）到 (i,j) 的路径数
int[][] dp = new int[m][n];
for(int j=0;j<n;j++){
if(obstacleGrid[0][j]==1){
break;
}else{
dp[0][j] = 1;
}
}
for(int i=0;i<m;i++){
if(obstacleGrid[i][0]==1){
break;
}else{
dp[i][0]=1;
}
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = (obstacleGrid[i][j]==0)?(dp[i-1][j] + dp[i][j-1]):0;
}
}
return dp[m-1][n-1];
}
@Test
public void test(){
int[][] grid={
{0,0,0},
{0,1,0},
{0,0,0}
};
//int[][] grid ={{1,0}};
System.out.println(uniquePathsWithObstacles(grid));
}