"逐步生成结果”类问题之数值型

自下而上的递归(递推数学归纳,动态规划)

• 递归又叫递推，不仅仅是只是自上而下的，这样写只是利用了编程语言的便捷性
• 自上向下只是代码的现象，只是写成了这种形式，而本质是由小规模问题形成大规模问题，是自下而上的
• 在数学上是数学归纳法

为什么是数学归纳法？

• 解决简单情况下的问题，如斐波那契数列假设前两项之和是第三项
• 推广到复杂情况，这个过程叫做归纳
• 上面两步就是递归
• 如果递推的次数很明确，就用迭代（循环，减少方法开辟的栈空间）
• 如果有封闭形式，可以直接求解

例1：CC150—9_1走楼梯

/** 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。 请实现一个方法，计算小孩有多少种上楼的方式。 为了防止溢出，请将结果Mod 1000000007 给定一个正整数int n，请返回一个数，代表上楼的方式数。 保证n小于等于100000。 */
public class _9_1走楼梯 {
  static final int mod = 1000000007;

  public static void main(String[] args) {
    System.out.println(recursion2(7));
    System.out.println(recursion1(7));
    System.out.println(recursion3(7));
  }

  /** * n较小的时候就会超时 * @param n * @return */
  public static long recursion1(int n) {
    if (n < 0) return 0;
    if (n == 0 || n == 1) return 1;
    if (n == 2) return 2;
    return recursion1(n - 1) % mod + recursion1(n - 2) % mod + recursion1(n - 3) % mod;
  }

  // 1 2 4 7 13 24 44
  public static int recursion2(int n) {
    if (n < 0) return 0;
    if (n == 0 || n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    int x1 = 1;
    int x2 = 2;
    int x3 = 4;
    for (int i = 4; i <= n; i++) {
      int x_1 = x1;
      x1 = x2 % mod;
      x2 = x3 % mod;
      x3 = ((x1 + x2) % mod + x_1) % mod;//注意此处
    }
    return x3;
  }

  public static int recursion3(int n) {
    long[][] base = {
        {0, 0, 1},
        {1, 0, 1},
        {0, 1, 1}};
    long[][] f1f2f3 = {{1, 2, 4}};
    return (int) Util.matrixMultiply(f1f2f3, Util.matrixPower(base, n - 1))[0][0];
  }
}

• 如果只有一个台阶，则只有一个解法
• 如果两个阶梯，走一步剩一个台阶，由于一个台阶只有一个解法，所以这走一步只有一个解法；走两步一个解法。所以两个台阶的是1 + 1 = 2种解法
• 如果三个阶梯，走一步剩两个台阶，由于两个个台阶只有两个个解法，所以这走两步步只有两个解法；走两步剩一个台阶，所以这走一步只有一个解法；走三步一个解法。所以三个台阶的是2 + 1 + 1 = 4种解法
• 依次迭代
• f(n) = f(n-1) + f(n-2) + f(n-3)

recursion2中(<mark>推荐用这种</mark>)

• x1,x2,x3其实代表着前三项，每次新算出一个数，不断的更新下个数的前三项
• 这是递归改循环

例2：CC150—9_2机器人走格子

**
 有一个X*Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。
 请设计一个算法，计算机器人有多少种走法。
 给定两个正整数int x,int y，请返回机器人的走法数目。保证x＋y小于等于12。
 */
public class _9_2机器人走格子 {
  public static void main(String[] args) {
    System.out.println(solve(6, 6));
    System.out.println(solve1(6, 6));
  }

  /** * 递归形式 * @param x * @param y * @return */
  public static int solve(int x, int y) {

    if (x == 1 || y == 1) return 1;

    return solve(x - 1, y) + solve(x, y - 1);
  }

  /** * 迭代形式 * @param m * @param n * @return */
  public static int solve1(int m, int n) {
    int[][] state = new int[m + 1][n + 1];
    for (int i = 1; i <= n; i++) {
      state[1][i] = 1;
    }
    for (int i = 1; i <= m; i++) {
      state[i][1] = 1;
    }
    for (int i = 2; i <= m; i++) {
      for (int j = 2; j <= n; j++) {
        state[i][j] = state[i][j - 1] + state[i - 1][j];
      }
    }
    return state[m][n];
  }

}

过程如下图所示

• 递推公式：f(x,y) = f(x-1,y) + f(x,y-1)
• 这道题跟公式里面是两个参数，所以在迭代时，采用的二维数组迭代，而上面的采用一维数组迭代
• 主要考虑公式里面变化的参数个数而选择不同维度的数组

例3：CC150—9_8硬币表示_经典

/** * 假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，用这些硬币组合构成一个给定的数值n。 * 例如n=200，那么一种可能的组合方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. * 问总共有多少种可能的组合方式？ (这道题目来自著名编程网站ProjectEuler) 类似的题目还有： 　　[华为面试题] 1分2分5分的硬币三种，组合成1角，共有多少种组合 1*x + 2*y + 5*z=10 　　[创新工厂笔试题] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少组合可以组成n分钱 1 5 10 25 分 n,多少种组合方法. */
public class _9_8硬币表示_经典 {
  public static void main(String[] args) {
    _9_8硬币表示_经典 obj = new _9_8硬币表示_经典();
    for (int i = 1; i < 101; i++) {
      int ways = obj.countWays(i);
      System.out.println(i + "---" + ways);
      ways = obj.countWays2(i);
      System.out.println(i + "---" + ways);
    }
  }

  int[][] state;

  /*递推解法*/
  public int countWays1(int n) {

    int[] coins = {1, 5, 10, 25};
    int[][] dp = new int[4][n + 1];//前i种面值,组合出面值j
    for (int i = 0; i < 4; i++) {
      dp[i][0] = 1;//凑出面值0,只有一种可能,第一列初始化为1
    }
    for (int j = 0; j < n + 1; j++) {
      dp[0][j] = 1;//用1来凑任何面值都只有一种凑法,第一行初始化为1
    }
    for (int i = 1; i < 4; i++) {
      for (int j = 1; j < n + 1; j++) {
        for (int k = 0; k <= j / coins[i]; ++k) {
          dp[i][j] += dp[i - 1][j - k * coins[i]];
        }
      }
    }
    return dp[3][n];
  }

  /*递推解法*/
  public int countWays2(int n) {

    int[] coins = {1, 5, 10, 25};
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 0; i < 4; i++) {
      for (int j = coins[i]; j < n + 1; j++) {
        dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007;
      }
    }
    return dp[n];
  }


/*递推解法--二维数组--推荐*/
    public int waysToChange(int n) {
        int [] coins = {1,5,10,25};
        int [] [] res = new int[4][n+1];
        for (int i = 0; i <= n; i++) {
            res[0][i] = 1 ;
        }
        for (int i = 0; i < 4; i++) {
            res[i][0] = 1;
        }
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j <= n; j++) {
                if (j>=coins[i]){
                    res[i][j] = (res[i-1][j]+res[i][j-coins[i]])%1000000007;

                }
                else {
                    res[i][j] = res[i-1][j];
                }
            }
        }
        return res[3][n];
    }


  /*递归形式*/
  public int countWays(int n) {
    if (n <= 0) return 0;
    return countWaysCore(n, new int[]{1, 5, 10, 25}, 3);
  }

  private int countWaysCore(int n, int[] coins, int cur) {
    if (cur == 0) return 1;
    int res = 0;
    //不选coins[cur]
    //要一个
    //要两个......
    for (int i = 0; i * coins[cur] <= n; i++) {
      int shengyu = n - i * coins[cur];
      res += countWaysCore(shengyu, coins, cur - 1);
    }
    return res;
  }

}