算法记录

• 动态规划
  • 使用
    1. 给最优解，最大最小值
    2. 计数，给方式
    3. 求存在性，选出k个数和为sum
  • 例题
    1. 最值型
       • 解题思路
         • 1）确定状态
           • 最后一步？
           • 子问题为？//问题一样，规模变小 最后一枚必定取自所知数组里：找出最小的一个组合数即可：
         • 2）转移方程
         • 3）准备两个步骤
           • • 初始条件//比较小的值定义出来
             • 边界情况//数组不要越界
         • 4）计算顺序
           • 一维，大多从小到大
           • 二维，从上到下，从左到右
           • 原因：等式左边要用到的状态，应当先于右边的状态值被计算出
         • 参考代码

           /* Your code... */public class Solution {
                                  //面额1,2,5      //总额11
               public int coinChange(int[] coins, int amount) {
                   //1.状态
                   int[] f= new int[amount + 1];
                   int n = coins.length;//硬币种类
           
                   //3初始化
                   f[0] = 0;
           
                   int i,j;
                   for (i = 1; i <= amount; ++i) {
                       //初始化为无穷,可以凑出再更改
                       f[i] = Integer.MAX_VALUE;
                       //System.out.println("初始化 f[ " + i +" ] = " + f[i]);
                       //最后一步
                       // 硬币必定出于coins[]
                       for (j = 0; j < n; ++j) { //边界条件: i >= coins[j]
                           //         f[i - coins[j]]不为无穷
                           if((i >= coins[j]) && (f[i - coins[j]] != Integer.MAX_VALUE)){
                                //2.转移方程
                                //f[i] = min(f[i - coins[0]] + 1，f[i - coins[1]] + 1，...)
                               f[i] = Math.min(f[(i - coins[j])] +1,f[i]);
                               //System.out.println("算得 f[ " + i +" ] = " + f[i]);
                           }
                           
                       }
                       
                   }
           
                   if(f[amount] == Integer.MAX_VALUE){
                           //无法组合输出-1
                           f[amount] = -1;
                   }
                   return f[amount];
                   
               }
               
           }

         • 最值问题小结
    2. 计数型
       • 1）确定状态
         • 最后一步： 
         • 转成子问题：
       • 2）转移方程：f[i][j] = f[i][j-1] +f[i-1][j]
       • 3）初始条件和边界情况
         • f[0][0] = 1;
         • f[i][0] = 1;
         • f[0][j] = 1;
       • 4）计算顺序
       • 参考代码

         /* Your code... */
         public class Solution {
             public int uniquePaths(int m, int n) {
                 // write your code here
                 int[][] f = new int[m][n];
                 int i,j;
                 f[0][0] = 1;
                 for(i = 0;i < m;++i){
                     for(j = 0;j < n;++j){
                         if(i == 0 || j == 0){ //边界条件
                              f[i][j] = 1;
                         }else{
                             f[i][j] = f[i][j -1] + f[i-1][j];//转移方程
                         }
                     }
                 }
                 return f[m-1][n-1];
         
             }
         }

    3. 存在型
       • 1）状态
         • 最后一步 ：在石头i上,能否到n-1上，n-1-i <= ai
         • 子问题：能否到i上 ？i – (i -1) >= a(i-1)
       • 2）转移方程
         • f[j] =   OR0<=i <j (f[i] AND i + a[i] >= j)
       • 3)初始化 f[0] = true;
         • 边界条件 无
       • 4）计算顺序
         • 从右往左
       • 参考代码

         /* Your code... */
         public class Solution {
             public boolean canJump(int[] a) {
                 // write your code here
                 //1状态
                 boolean[] f = new boolean[a.length];
                 //2初始化
                 f[0] = true;
                 //3转移方程
                 int i,j;
                 for(j = 1;j < a.length;++j){
                     f[j] = false;
                     for(i = 0;i < j;++i){
                         if(f[i] && a[i] + i >= j){
                             f[j] = true; 
                             break;
                         }
                     }
                 }
                 return f[a.length-1];
         
             }
         }

参考 九章算法-动态规划专题班