动态规划算法

动态规划是怎么的来的？

题目1 —— 钱币兑换问题：

给一个正数数组，且不重复，每个值代表一种货币的面值，每种货币可以使用任意张，给定一个整数aim表示钱数，求有多少种换钱的方式。

解法一：DFS暴力搜索

>//函数表示 利用arr[idx...arr.length-1]中的货币面值可以得到的aim的方法数
>public int dfs(int[] arr, int idx,int aim){
   if(idx == arr.length){
       return aim ==0:1?0;
   }
   int cnt = 0;
   for(int i=0; arr[idx] * i <=aim;i++ ){
       cnt += dfs(arr, idx+1, aim - arr[idx]*i);
   }
   return cnt;
>}

解法二：记忆搜索

>//函数表示 利用arr[idx...arr.length-1]中的货币面值可以得到的aim的方法数
>int[][] dp = new int[arr.length][aim+1];
>public int dfs(int[] arr, int idx,int aim){
   if(idx == arr.length){
       return aim ==0:1?0;
   }
   int cnt = 0;
   int val = 0;
   for(int i=0; arr[idx] * i <=aim;i++ ){
       if(dp[idx+1,aim - arr[idx]*i] != -1){
           val = dp[idx+1,aim - arr[idx]*i];
       }else{
           val = dfs(arr, idx+1, aim - arr[idx]*i);
       }
       cnt += val;
   }
   dp[idx,aim] = cnt;
   return cnt;
>}

解法三：DP

使用一个二维数组 arr [N] [aim+1] 表示状态，其中arr [i] [j] 表示0~i 的货币面值组成 钱数为j的 所有可能的组合

数，所以假如面值数组为 = {1，3，5，20}，目标金额为30

1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
1
1
1

如图表示 第一行 arr[0] [0….20] 表示只用面值为1的金币组成0元、1元、等到20元，都只有一种组合方式，那就是全部使用面值为1元的金币。第一列arr [0…3] [0]表示使用任意面值的金币组成0元的金额，那么只有一种组合就是使用0张。此为所有的初始状态。

那么对于 arr [i] [j] 来说呢

1. 假如使用0张 面值【i】的金币，则有 arr[i-1] [j] 中组合方式
2. 假如使用1张 面值【i】的金币，则有 arr[i-1] [j - 面值【i】] 的组合方式
3. 假如使用2张 面值【i】的金币，则有 arr[i-1] [j - 2 * 面值【i】] 的组合方式
4. 。。。。

以此类推 并将每一种结果进行累加，即可得到最终的值

>int[][] dp = new int[N][aim];
>int[] arr = new int[N];//表示不同的金币面值数组
>//初始化
>for(int i=0;i<N;i++){
   dp[i][0] = 1;//对于目标金额为0 只有1中方法，使用0张
>}
>for(int i=1;i<=aim ;i++){
   if(i % arr[0] == 0){ //只使用arr【0】面值的时候，只有金额是其整数倍，才能组成目标金额
 		dp[0][i] = 1;
   }
>}
>//对剩余的二维数组  从左到右 计算每一行，然后计算下一行
>for(int i=1;i<N;i++){
   
   for(int j=1; j<=aim;j++){ //遍历目标金额值
       
       int cnt = 0;
       for(int k = 0; arr[i] * k <= j; k++){
           cnt += dp[i-1][aim - arr[i]*k];
       }
       dp[i][j] = cnt;
   }
>}
>//保存结果
>int res = arr[N-1][aim];

总结：

动态规划 算法是由 暴力搜索 –> 记忆化暴力搜索 –> 动态规划 一步步优化而来的

1. 首先使用暴力搜索可以解决问题，但是暴力搜索会导致冗余或者说重复的计算，因此效率比较低
2. 对于暴力搜索可以使用记忆的方式进行优化，去掉重复计算，此时计算时间复杂度已经接近与动态规划了
3. 动态规划和记忆搜索的区别在于，动态规划是可以提前根据状态转移方程规定好，计算的步骤，从初始状态一步步递推得到最后的结果的算法。