优化路线：

try（递归尝试）-> 记忆化搜索（dp）-> 严格表结构（dp）-> 严格表结构高精（dp）
try（递归尝试）：会产生重复计算，浪费时间
记忆化搜索：用一个缓存来缓存之前的数据，避免重复计算。不整理位置之间的依赖关系。
严格表结构：纠结位置之间的依赖顺序。
做动态规划的题目，首先进行递归尝试，然后优化成记忆化搜索，最后根据位置的依赖关系，转换成严格表结构，直接将递归尝试的代码，复制然后进行边界修改，不需要的进行删除。
严格表结构高精：在严格表结构的基础上进行观察产生的

决定暴力尝试好坏的因素有哪些？

  1. 单个可变参数的维度，最好是一个整数，最好不要用一个数组来表示不确定的状态。

  2. 可变参数的个数少的好。一维就是一行值，二维是一个二维表，三维就是一个立体。

    阿里笔试题：机器人走K步到达M点问题

  3. 假设有排成一行的N个位置，记为1~N，N一定大于或等于2;

  4. 开始时机器人在M（1 <= M <= N）位置上，
  5. 如果机器人位于1位置，那么下一步只能走到2位置，
  6. 如果机器人位于N位置，那么下一步只能走到N-1位置，
  7. 如果机器人位于中间的任一位子，那么下一步可以向左走，也可以向右走。

  8. 机器人必须走K步，最终来到P（1 <= P <= N），给定参数N，M，K，P，有多少种走法？

    1. public class RobotWalk {
    3.  public static int ways1(int N, int M, int K, int P) {
    4.      // 参数无效直接返回0
    5.      if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
    6.          return 0;
    7.      }
    8.      // 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
    9.      return walk(N, M, K, P);
    10.  }
    11.  // 递归版本
    12.  // N : 位置为1 ~ N，固定参数
    13.  // cur : 当前在cur位置，可变参数
    14.  // rest : 还剩res步没有走，可变参数
    15.  // P : 最终目标位置是P，固定参数
    16.  // 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，
    17.  // 停在P位置的方法数作为返回值返回
    18.  // 这种方式会产生重复计算，浪费时间
    19.  // f(N,4,2,P) --> f(N,3,1,P)、f(N,3,3,P)
    20.  // f(N,3,1,P) --> f(N,2,2,P)
    21.  // f(N,3,3,P) --> f(N,2,2,P)、f(N,2,4,P)
    22.  public static int walk(int N, int cur, int rest, int P) {
    23.      // 如果没有剩余步数了，当前的cur位置就是最后的位置
    24.      // 如果最后的位置停在P上，那么之前做的移动是有效的
    25.      // 如果最后的位置没在P上，那么之前做的移动是无效的
    26.      if (rest == 0) {
    27.          return cur == P ? 1 : 0;
    28.      }
    29.      // 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
    30.      // 后续的过程就是，来到2位置上，还剩rest-1步要走
    31.      if (cur == 1) {
    32.          return walk(N, 2, rest - 1, P);
    33.      }
    34.      // 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
    35.      // 后续的过程就是，来到N-1位置上，还剩rest-1步要走
    36.      if (cur == N) {
    37.          return walk(N, N - 1, rest - 1, P);
    38.      }
    39.      // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
    40.      // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
    41.      // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
    42.      // 走向左、走向右是截然不同的方法，所以总方法数要都算上
    43.      return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
    44.  }
    46.  // 对上面方式进行记忆化搜索
    47.  public static int ways1(int N, int M, int K, int P) {
    48.      if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
    49.          return 0;
    50.      }
    51.      int[][] dp = new int[K + 1][N + 1];
    52.      for (int i = 0; i <= K; i++) {
    53.          for (int j = 0; j <= N; j++) {
    54.              dp[i][j] = -1;
    55.          }
    56.      }
    57.      return walk(N, M, K, P,dp);
    58.  }
    59.  public static int walk(int N, int cur, int rest, int P,int[][] dp) {
    60.      if (dp[rest][cur] != -1) {
    61.          return dp[rest][cur];
    62.      }
    63.      if (rest == 0) {
    64.          dp[rest][cur] = cur == P ? 1 : 0;
    65.          return dp[rest][cur];
    66.      }
    68.      if (cur == 1) {
    69.          dp[rest][cur] = walk(N, 2, rest - 1, P,dp);
    70.      } else if (cur == N) {
    71.          dp[rest][cur] = walk(N, N - 1, rest - 1, P,dp);
    72.      } else {
    73.          dp[rest][cur] = walk(N, cur + 1, rest - 1, P,dp) + 
    74.              walk(N, cur - 1, rest - 1, P,dp);
    75.      }
    77.      return dp[rest][cur];
    78.  }
    80.  public static int ways2(int N, int M, int K, int P) {
    81.      // 参数无效直接返回0
    82.      if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
    83.          return 0;
    84.      }
    85.      int[][] dp = new int[K + 1][N + 1];
    86.      dp[0][P] = 1;
    87.      for (int i = 1; i <= K; i++) {
    88.          for (int j = 1; j <= N; j++) {
    89.              if (j == 1) {
    90.                  dp[i][j] = dp[i - 1][2];
    91.              } else if (j == N) {
    92.                  dp[i][j] = dp[i - 1][N - 1];
    93.              } else {
    94.                  dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
    95.              }
    96.          }
    97.      }
    98.      return dp[K][M];
    99.  }
    101.  public static int ways3(int N, int M, int K, int P) {
    102.      // 参数无效直接返回0
    103.      if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
    104.          return 0;
    105.      }
    106.      int[] dp = new int[N + 1];
    107.      dp[P] = 1;
    108.      for (int i = 1; i <= K; i++) {
    109.          int leftUp = dp[1];// 左上角的值
    110.          for (int j = 1; j <= N; j++) {
    111.              int tmp = dp[j];
    112.              if (j == 1) {
    113.                  dp[j] = dp[j + 1];
    114.              } else if (j == N) {
    115.                  dp[j] = leftUp;
    116.              } else {
    117.                  dp[j] = leftUp + dp[j + 1];
    118.              }
    119.              leftUp = tmp;
    120.          }
    121.      }
    122.      return dp[M];
    123.  }
    125.  public static void main(String[] args) {
    126.      System.out.println(ways1(7, 4, 9, 5));
    127.      System.out.println(ways2(7, 4, 9, 5));
    128.      System.out.println(ways3(7, 4, 9, 5));
    129.  }
    130. }

    给一个int[]{2,7,3,5,3}正数，里面的值代表一枚硬币的面值，一个数就代表一枚硬币，给你一个数，假如是10，用最少的硬币组成10这个数

    从左往右模型，从左往右进行遍历尝试

    1.  // 暴力尝试
    2.  public static int minCoins(int[] arr, int aim) {
    3.      return process(arr, 0, aim);
    4.  }
    5.  // arr[index...]组成出rest这么多钱，最少的硬币数量返回
    6.  public static int process(int[] arr,int index, int rest) {
    7.      if (rest < 0) {
    8.          return -1;
    9.      }
    11.      if (rest == 0) {
    12.          return 0;
    13.      }
    15.      // rest > 0
    16.      if (index == arr.length) {
    17.          return -1;
    18.      }
    19.      // rest > 0 并且 也有硬币
    20.      int p1 = process(arr, index + 1, rest);
    21.      int p2Next = process(arr, index + 1, rest - arr[index]);
    22.      if (p1 == -1 && p2Next == -1) {
    23.          return -1;
    24.      } else {
    25.          if (p1 == -1) {
    26.              return p2Next + 1;
    27.          }
    28.          if (p2Next == -1) {
    29.              return p1;
    30.          }
    31.          return Math.min(p1, p2Next + 1);
    32.      }
    33.  }
    35.  // 记忆化搜索
    36.  public static int minCoins(int[] arr, int aim) {
    37.      int[][] dp = new int[arr.length + 1][aim + 1];
    38.      for (int i = 0; i <= arr.length; i++) {
    39.          for (int j = 0; j <=aim; j++) {
    40.              dp[i][j] = -2;
    41.          }
    42.      }
    43.      return process(arr, 0, aim, dp);
    44.  }
    45.  // arr[index...]组成出rest这么多钱，最少的硬币数量返回
    46.  public static int process(int[] arr,int index, int rest, int[][] dp) {
    47.      if (rest < 0) {
    48.          return -1;
    49.      }
    51.      if (dp[index][rest] != -2) {
    52.          return dp[index][rest];
    53.      }
    55.      if (rest == 0) {
    56.          dp[index][rest] = 0;
    57.      } else if (index == arr.length) {
    58.          dp[index][rest] = -1;
    59.      } else {
    60.          int p1 = process(arr, index + 1, rest,dp);
    61.          int p2Next = process(arr, index + 1, rest - arr[index],dp);
    63.          if (p1 == -1 && p2Next == -1) {
    64.              dp[index][rest] = -1;
    65.          } else {
    66.              if (p1 == -1) {
    67.                  dp[index][rest] = p2Next + 1;
    68.              } else if (p2Next == -1) {
    69.                  dp[index][rest] = p1;
    70.              } else {
    71.                  dp[index][rest] = Math.min(p1, p2Next + 1);
    72.              }
    73.          }
    74.      }
    75.      return dp[index][rest];
    76.  }
    78.  // 严格表结构
    79.  public static int minCoins(int[] arr, int aim) {
    80.      int N = arr.length;
    81.      int[][] dp = new int[N + 1][aim + 1];
    83.      for (int row = 0; row <= N; row++) {
    84.          dp[row][0] = 0;
    85.      }
    87.      for (int col = 1; col <= aim; col++) {
    88.          dp[N][col] = -1;
    89.      }
    91.      for (int index = N - 1; index >= 0; index--) {
    92.          for (int rest = 1; rest <= aim; rest++) {
    94.              int p1 = dp[index + 1][rest];
    95.              int p2Next = -1;
    96.              if (rest - arr[index] >= 0) {
    97.                  p2Next = dp[index + 1][rest - arr[index]];
    98.              }
    99.              // rest > 0 并且 也有硬币
    100.              if (p1 == -1 && p2Next == -1) {
    101.                  dp[index][rest] = -1;
    102.              } else {
    103.                  if (p1 == -1) {
    104.                      dp[index][rest] = p2Next + 1;
    105.                  }
    106.                  if (p2Next == -1) {
    107.                      dp[index][rest] = p1;
    108.                  }
    109.                  dp[index][rest] = Math.min(p1, p2Next + 1);
    110.              }
    112.          }
    113.      }
    115.      return dp[0][aim];
    116.  }
    1. // 无效解不能返回0，返回0算是有解，解就0个硬币
    2. public class CoinsMin {
    4.  public static int minCoins1(int[] arr, int aim) {
    5.      if (arr == null || arr.length == 0 || aim < 0) {
    6.          return -1;
    7.      }
    8.      return process(arr, 0, aim);
    9.  }
    11.  // 当前考虑的面值是arr[i]，还剩rest的钱需要找零
    12.  // 如果返回-1说明自由使用arr[i..N-1]面值的情况下，无论如何也无法找零rest
    13.  // 如果返回不是-1，代表自由使用arr[i..N-1]面值的情况下，找零rest需要的最少张数
    14.  public static int process(int[] arr, int i, int rest) {
    15.      // base case：
    16.      // 已经没有面值能够考虑了
    17.      // 如果此时剩余的钱为0，返回0张
    18.      // 如果此时剩余的钱不是0，返回-1
    19.      if (i == arr.length) {
    20.          return rest == 0 ? 0 : -1;
    21.      }
    22.      // 最少张数，初始时为-1，因为还没找到有效解
    23.      int res = -1;
    24.      // 依次尝试使用当前面值(arr[i])0张、1张、k张，但不能超过rest
    25.      for (int k = 0; k * arr[i] <= rest; k++) {
    26.          // 使用了k张arr[i]，剩下的钱为rest - k * arr[i]
    27.          // 交给剩下的面值去搞定(arr[i+1..N-1])
    28.          int next = process(arr, i + 1, rest - k * arr[i]);
    29.          if (next != -1) { // 说明这个后续过程有效
    30.              res = res == -1 ? next + k : Math.min(res, next + k);
    31.          }
    32.      }
    33.      return res;
    34.  }
    36.  public static int minCoins2(int[] arr, int aim) {
    37.      if (arr == null || arr.length == 0 || aim < 0) {
    38.          return -1;
    39.      }
    40.      int N = arr.length;
    41.      int[][] dp = new int[N + 1][aim + 1];
    42.      // 设置最后一排的值，除了dp[N][0]为0之外，其他都是-1
    43.      for (int col = 1; col <= aim; col++) {
    44.          dp[N][col] = -1;
    45.      }
    46.      for (int i = N - 1; i >= 0; i--) { // 从底往上计算每一行
    47.          for (int rest = 0; rest <= aim; rest++) { // 每一行都从左往右
    48.              dp[i][rest] = -1; // 初始时先设置dp[i][rest]的值无效
    49.              if (dp[i + 1][rest] != -1) { // 下面的值如果有效
    50.                  dp[i][rest] = dp[i + 1][rest]; // dp[i][rest]的值先设置成下面的值
    51.              }
    52.              // 左边的位置不越界并且有效
    53.              if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1) {
    54.                  if (dp[i][rest] == -1) { // 如果之前下面的值无效
    55.                      dp[i][rest] = dp[i][rest - arr[i]] + 1;
    56.                  } else { // 说明下面和左边的值都有效，取最小的
    57.                      dp[i][rest] = Math.min(dp[i][rest],
    58.                              dp[i][rest - arr[i]] + 1);
    59.                  }
    60.              }
    61.          }
    62.      }
    63.      return dp[0][aim];
    64.  }
    66.  // for test
    67.  public static int[] generateRandomArray(int len, int max) {
    68.      int[] arr = new int[(int) (Math.random() * len) + 1];
    69.      for (int i = 0; i < arr.length; i++) {
    70.          arr[i] = (int) (Math.random() * max) + 1;
    71.      }
    72.      return arr;
    73.  }
    75.  public static void main(String[] args) {
    76.      int len = 10;
    77.      int max = 10;
    78.      int testTime = 10000;
    79.      for (int i = 0; i < testTime; i++) {
    80.          int[] arr = generateRandomArray(len, max);
    81.          int aim = (int) (Math.random() * 3 * max) + max;
    82.          if (minCoins1(arr, aim) != minCoins2(arr, aim)) {
    83.              System.out.println("ooops!");
    84.              break;
    85.          }
    86.      }
    87.  }
    88. }