Skip to content

7_动态规划.md

Latest commit

 

History

History
1441 lines (1171 loc) · 31.9 KB

7_动态规划.md

File metadata and controls

1441 lines (1171 loc) · 31.9 KB
Raw

动态规划

一、管窥动态规划

1、斐波那契数列

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");
}

2、动态规划的解释

动态规划就是将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

二、常见的动态规划问题

*1、爬楼梯（70）

70. 爬楼梯

//思路一：递归
//分析（自顶向下）：
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));
}

2、三角形最小路径和（120）

120. 三角形最小路径和

//思路：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));
}

3、杨辉三角(118)

118. 杨辉三角

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);
    }
}

*4、打家劫舍（198）

198. 打家劫舍

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));
}

5、打家劫舍 II（213）

213. 打家劫舍 II

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));
}

三、分割整数

*1、整数拆分（343）

343. 整数拆分

//思路：
//思路一：递归 + 记忆化素搜索的方式
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));
}

2、完全平方数（279）

279. 完全平方数

//思路：类似 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));
}

3、解码方法（91）

91. 解码方法

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));
}

*四、0-1 背包问题

1、0-1 背包问题

  • 问题描述：

有一个背包，它的容量为 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]);
  }
}

2、0-1 背包问题的优化

上面的 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
}

3、分割等和子集（416）

416. 分割等和子集

//思路：实际上是 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));
}

4、目标和（494）

目标和

//思路：
//假设原数组为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));
}

5、组合总和 Ⅳ（377）

377. 组合总和 Ⅳ

//思路：实际上是 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));
}

*6、零钱兑换（322）

零钱兑换

//思路：因为硬币可以重复使用，因此这是一个完全背包问题。
//完全背包只需要将 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));
}

7、零钱兑换II（518）

//思路：完全背包问题
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));
}

*8、一和零(474)

一和零

//思路：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];
}

139

377

四、数组区间

303

413

四、LIS 问题

300

646

376

五、LCS 问题

六、矩阵路径

*1、最小路径和（64）

64. 最小路径和

//思路：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;
}

2、不同路径（62）

62. 不同路径

//思路一：动态规划
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));
}

3、不同路径 II(63)

63. 不同路径 II

//思路：其实与 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));
}