DP1

2020-04-09

动态规划(Dynamic Programming)

求解最优化问题的一种常用策略
通常的使用套路（一步一步优化）
- 暴力递归（自顶向下，出现了重叠子问题）
- 记忆化搜索（自顶向下）
- 递推（自底向上）
动态规划中的“动态”可以理解为是“会变化的状态”
- 定义状态（状态是原问题、子问题的解）
- 设置初始状态（边界）
- 确定状态转移方程

假设有25分、20分、5分、1分的硬币，现在要找给客户41分的零钱，如何办到硬币个数最少

如果使用贪心策略，我们将优先选择最大的硬币，即25->5->5->5->1,一共需要找5个硬币，但很明显，这并不是最优解.
我们只需要大致想一下，最优解应该为20->20->1，一共三个硬币.
接下来我们使用动态规划的思路来求解这个问题.

假设dp(n)是凑到n分需要的最少硬币个数
- 如果我们第一次选择25分的硬币，那么dp(n)=dp(n-25)+1.
- 如果我们第一次选择20分的硬币，那么dp(n)=dp(n-20)+1.
- 如果我们第一次选择5分的硬币，那么dp(n)=dp(n-5)+1.
- 如果我们第一次选择1分的硬币，那么dp(n)=dp(n-1)+1.
即dp(n)=min{dp(n-25),dp(n-20),dp(n-5),dp(n-1)}+1

public class Main{
 public static void main(String []args){
   System.out.println(coins(41));
   
 }
  static int coins(int n){
    if(n<=0) return -1;
    if(n==25||n==20||n==5||n==1) return 1;
    
    int min1=Math.min(coins(n-25),coins(n-20));
    int min2=Math.min(coins(n-5),coins(n-1));
    return Math.min(min1,min2)+1;
    
  }
}

将上述想法转换成代码，我们可以得到正确答案，最少为3个硬币。

通过上面的过程，明显可以看得出来是一个递归过程，就像我们最开始求斐波那契数一样。

static int fib(int n){
  if(n<=2) return 1;
  return fib(n-1)+fib(n-2);
}

这就是我们刚才讲的第一种境界：“暴力递归”

不出意外地，我们会进行很多重复的计算，即出现了重叠子问题.

接下来我们采用记忆化搜索，对其进行优化

public class Main{
 public static void main(String []args){
   System.out.println(coins(41));
   
 }
  static int coins(int n){
    //不合理情况
    if(n<=0) return -1;
    int dp[]=new int [n+1];
    dp[1]=dp[5]=dp[20]=dp[25]=1;
    return coins(n,dp);
  }
  static int coins(int n,int []dp){
    
    //初始情况
    if(dp[n]==0){
      if(n<=0) return -1:
       int min1=Math.min(coins(n-25),coins(n-20));
       int min2=Math.min(coins(n-5),coins(n-1));
      dp[n]=Math.min(min1,min2)+1;
      
    }
    return dp[n];
  }
}

即我们利用dp数组存储了可能算过的值，叫做“记忆化搜索”，对上述暴力递归进行了优化。

当然，这也不是动态规划！

接下来我们利用动态规划来解决这个问题

public class Main{
 public static void main(String []args){
   System.out.println(coins(41));
   
 }
  static int coins(int n){
    if(n<=0) return -1;
    int dp[]=new int [n+1];
    for(int i=1;i<=n;i++){
      int min=Integer.MAX_VALUE;
      if(i>=1) 
        min=Math.min(dp[i-1],min);
      if(i>=5)
        min=Math.min(dp[i-5],min);
      if(i>=20)
        min=Math.min(dp[i-20],min);
      if(i>=25)
        min=Math.min(dp[i-25],min);
      dp[n]=min+1;
       }
    return dp[n];
  }
 
}

以上就是动态规划的思想了，也就是递推法！

如果想知道每次取的是哪几个硬币，我们也可以稍微修改一下上述代码

public class Main{
 public static void main(String []args){
		   System.out.println(coins(41));
		   
		 }
		  static int coins(int n){
		    if(n<=0) return -1;
		    int dp[]=new int [n+1];
		    //ans[i]为凑够i分时最后选择的硬币
		    //即ans[n]为凑够n分时最后选择的硬币
		    int ans[]=new int [dp.length];
		    for(int i=1;i<=n;i++){
		      int min=Integer.MAX_VALUE;
		      if(i>=1&&dp[i-1]<min) {
		    	  min=dp[i-1];
			      ans[i]=1;
		      }
		      if(i>=5&&dp[i-5]<min) {
		    	  min=dp[i-5];
			      ans[i]=5;
		      }
		      if(i>=20&&dp[i-20]<min) {
		    	  min=dp[i-20];
			      ans[i]=20;
		      }
		      if(i>=25&&dp[i-25]<min) {
		    	   min=dp[i-25];
				      ans[i]=25;
		      }
		      dp[i]=min+1;
		       }
		    print(ans,n);
		    return dp[n];
		  }
		  static void print(int ans[],int n){
		    //n-ans[n]剩下要凑的硬币
		  while(n>0){
		    System.out.println(ans[n]);
		    n=n-ans[n];
		  }
		    }
}

通过上述方案，我们就可以得到取出的是哪一些硬币。
LeetCode 322、零钱兑换
https://leetcode-cn.com/problems/coin-change/
有了上面的思路，我们要实现一般化的过程也很简单。

class Solution {
    public int coinChange(int[] coins, int amount) {
       if(amount<0||coins.length==0||coins==null) return -1;
       int dp[]=new int[amount+1];
       
       for(int i=1;i<=amount;i++){
         int min=Integer.MAX_VALUE;
           for(Integer coin:coins){
              if(i<coin||dp[i-coin]<0) continue;
              min=Math.min(min,dp[i-coin]);
       }
       if(min==Integer.MAX_VALUE){
           dp[i]=-1;
       }else{
           dp[i]=min+1;
       } 
    }
    return dp[amount];
}
}