两个人玩游戏，有几个数字【2，100，30，5】只能拿最左或者最右的，最后看谁哪的分数高。

前面有暴力递归的代码

  1. // 动态规划
  2.     public static int win2(int[] arr) {
  3.         if (arr == null || arr.length == 0) {
  4.             return 0;
  5.         }
  6.         int[][] f = new int[arr.length][arr.length];
  7.         int[][] s = new int[arr.length][arr.length];
  8.         for (int j = 0; j < arr.length; j++) {
  9.             f[j][j] = arr[j];
  10.             for (int i = j - 1; i >= 0; i--) {
  11.                 f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
  12.                 s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
  13.             }
  14.         }
  15.         return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
  16.     }

三维表

象棋棋盘上标一个点（x,y），让马跳到这个点，而且还得跳k步。

  1. public class HorseJump {
  3.     public static int getWays(int x, int y, int step) {
  4.         return process(x, y, step);
  5.     }
  6.     // 潜台词：从（0，0）位置出发
  7.     // 要去往（x，y）位置，必须跳step步
  8.     // 返回方法数
  9.     public static int process(int x, int y, int step) {
  10.         if (x < 0 || x > 8 || y < 0 || y > 9) {
  11.             return 0;
  12.         }
  13.         if (step == 0) {
  14.             return (x == 0 && y == 0) ? 1 : 0;
  15.         }
  16.         // 要到达的位置不越界，也有步数可以跳
  17.         return process(x - 1, y + 2, step - 1)
  18.                 + process(x + 1, y + 2, step - 1)
  19.                 + process(x + 2, y + 1, step - 1)
  20.                 + process(x + 2, y - 1, step - 1)
  21.                 + process(x + 1, y - 2, step - 1)
  22.                 + process(x - 1, y - 2, step - 1)
  23.                 + process(x - 2, y - 1, step - 1)
  24.                 + process(x - 2, y + 1, step - 1);
  25.     }
  26.     // 动态规划 严格表结构
  27.     public static int dpWays(int x, int y, int step) {
  28.         if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) {
  29.             return 0;
  30.         }
  31.         int[][][] dp = new int[9][10][step + 1];
  32.         dp[0][0][0] = 1;
  33.         for (int h = 1; h <= step; h++) {
  34.             for (int r = 0; r < 9; r++) {
  35.                 for (int c = 0; c < 10; c++) {
  36.                     dp[r][c][h] += getValue(dp, r - 1, c + 2, h - 1);
  37.                     dp[r][c][h] += getValue(dp, r + 1, c + 2, h - 1);
  38.                     dp[r][c][h] += getValue(dp, r + 2, c + 1, h - 1);
  39.                     dp[r][c][h] += getValue(dp, r + 2, c - 1, h - 1);
  40.                     dp[r][c][h] += getValue(dp, r + 1, c - 2, h - 1);
  41.                     dp[r][c][h] += getValue(dp, r - 1, c - 2, h - 1);
  42.                     dp[r][c][h] += getValue(dp, r - 2, c - 1, h - 1);
  43.                     dp[r][c][h] += getValue(dp, r - 2, c + 1, h - 1);
  44.                 }
  45.             }
  46.         }
  47.         return dp[x][y][step];
  48.     }
  50.     public static int getValue(int[][][] dp, int row, int col, int step) {
  51.         if (row < 0 || row > 8 || col < 0 || col > 9) {
  52.             return 0;
  53.         }
  54.         return dp[row][col][step];
  55.     }
  57.     public static void main(String[] args) {
  58.         int x = 7;
  59.         int y = 7;
  60.         int step = 10;
  61.         System.out.println(getWays(x, y, step));
  62.         System.out.println(dpWays(x, y, step));
  63.     }
  64. }

给一个N*M大小的表格，bob在（x,y）的位置，如果bob出了界就会死，一个k表示bob能走几步，他每一步等概率上下左右随机走，求他活下来的概率

  1. public class BobDie {
  3.     public static String bob1(int N, int M, int i, int j, int K) {
  4.         long all = (long) Math.pow(4, K);
  5.         long live = process(N, M, i, j, K);
  6.         long gcd = gcd(all, live);
  7.         return String.valueOf((live / gcd) + "/" + (all / gcd));
  8.     }
  10.     public static long process(int N, int M, int row, int col, int rest) {
  11.         if (row < 0 || row == N || col < 0 || col == M) {
  12.             return 0;
  13.         }
  14.         if (rest == 0) {
  15.             return 1;
  16.         }
  17.         long live = process(N, M, row - 1, col, rest - 1);
  18.         live += process(N, M, row + 1, col, rest - 1);
  19.         live += process(N, M, row, col - 1, rest - 1);
  20.         live += process(N, M, row, col + 1, rest - 1);
  21.         return live;
  22.     }
  24.     public static long gcd(long m, long n) {
  25.         return n == 0 ? m : gcd(n, m % n);
  26.     }
  28.     public static String bob2(int N, int M, int i, int j, int K) {
  29.         int[][][] dp = new int[N + 2][M + 2][K + 1];
  30.         for (int row = 1; row <= N; row++) {
  31.             for (int col = 1; col <= M; col++) {
  32.                 dp[row][col][0] = 1;
  33.             }
  34.         }
  35.         for (int rest = 1; rest <= K; rest++) {
  36.             for (int row = 1; row <= N; row++) {
  37.                 for (int col = 1; col <= M; col++) {
  38.                     dp[row][col][rest] = dp[row - 1][col][rest - 1];
  39.                     dp[row][col][rest] += dp[row + 1][col][rest - 1];
  40.                     dp[row][col][rest] += dp[row][col - 1][rest - 1];
  41.                     dp[row][col][rest] += dp[row][col + 1][rest - 1];
  42.                 }
  43.             }
  44.         }
  45.         long all = (long) Math.pow(4, K);
  46.         long live = dp[i + 1][j + 1][K];
  47.         long gcd = gcd(all, live);
  48.         return String.valueOf((live / gcd) + "/" + (all / gcd));
  49.     }
  51.     public static void main(String[] args) {
  52.         int N = 10;
  53.         int M = 10;
  54.         int i = 3;
  55.         int j = 2;
  56.         int K = 5;
  57.         System.out.println(bob1(N, M, i, j, K));
  58.         System.out.println(bob2(N, M, i, j, K));
  59.     }
  60. }

arr里都是正数，没有重复值，每一个值代表一种货币，每一种都可以用无限张，最终要找零钱数是aim，找零方法数返回

// 暴力递归
public static int process (int arr[], int index,int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        // arr[index] 0张 1张。。。 不要超过rest的钱数
        int result = 0;
        for (int zhang = 0; zhang * arr[index] < rest; zhang++) {
            result += process(arr, index + 1, rest - zhang * arr[index]);
        }
        return result;
    }
// 动态规划
public static int way (int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        dp[N][0] = 1;

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
                    ways += dp[index + 1][rest - arr[index] * zhang];
                }
                dp[index][rest] = ways;
            }
        }

        return dp[0][aim];
    }

上一题在用动态规划求的时候，会产生一个枚举行为

暴力递归-上 - 图1
暴力递归-上 - 图2
image.pngimage.png 

public static int way (int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];

        dp[N][0] = 1;

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }

        return dp[0][aim];
    }