动态规划-记忆化搜索 - 《算法专题》

:::warning dfs + 搜索
记忆化搜索，本质还是 动态规划，只是实现方式采用了 深度优先搜索 的形式，但是它不像 深度优先搜索那样重复枚举所有情况，而是把已经计算的子问题保存下来，典型的空间换时间的思想。 :::

单词拆分

:::warning 用数组 int[] memo 记录搜索过的值
memo[i] 表示 s.substring(0,i) + 字典 是否能拼接出 s
-1 未选择
0 不能拼接
1 能拼接 :::

class Solution {
    int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dfs(0, s, wordDict);
    }
    boolean dfs(int idx, String s, List<String> wordDict) {
        if (idx == s.length()) {
            return true;
        }
        if (memo[idx] != -1) {
            return memo[idx] == 0 ? false : true;
        }
        for (String word : wordDict) {
            int len = word.length();
            //1 长度大于原字符串, 无法拼接
            if (idx + len > s.length()) {
                continue;
            }
            String sbstr = s.substring(idx, idx + len);
            //2 字符串不相等, 无法拼接
            if (!sbstr.equals(word)) {
                continue;
            }
            //3 可拼接
            if (dfs(idx + len, s, wordDict)) {
                memo[idx] = 1;
                return true;
            }
        }
        memo[idx] = 0;
        return false;
    }
}

整数替换

:::warning 用 map 记录计算过的 n :::

class Solution {
    Map<Long, Integer> memo = new HashMap<>();
    public int integerReplacement(int n) {
        return dfs((long)n);
    }
    int dfs(long cur) {
        if (cur == 1) {
            return 0;
        }
        if (memo.containsKey(cur)) {
            return memo.get(cur);
        }
        int ans = 0;
        if (cur % 2 == 0) {
            ans = dfs(cur / 2) + 1;
        } else {
            ans = Math.min(dfs(cur + 1), dfs(cur - 1)) + 1;
        }
        memo.put(cur, ans);
        return ans;
    }
}

跳跃游戏

法1 记忆化搜索 :::warning 用数组 int[] memo 记录搜索过的值
-1 不能到达
0 未计算
1 能到达
dfs(idx) == 1 表示 idx 是否能到达尾部。
能到达尾部的前提是 最后一个节点 前面有元素能到达尾部
具体而言即 i + nums[i] >= idx && dfs(i) == 1 :::

class Solution {
  int[] nums;
  public boolean canJump(int[] nums){
      memo = new int[nums.length];
      this.nums = nums;
      //第一个一定能到达
      memo[0] = 1;
      return dfs(nums.length - 1) == 1;
  }
  private int dfs(int idx){
      if (memo[idx] != 0){
          return memo[idx];
      }
      //能到达尾部的前提是 nums[nums.length - 1]前面有元素能到达尾部
      //具体而言即 i + nums[i] >= idx && dfs(i) == 1
      for (int i = idx - 1; i >= 0; i--) {
          if (i + nums[i] >= idx && dfs(i) == 1) {
              return memo[idx] = 1;
          }
      }
      return memo[idx] = -1;
  }
}

法2 贪心 :::warning 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
可以对每一个能作为起跳点的格子都尝试跳一次，把 能跳到最远的距离 不断更新,如果可以一直跳到最后，就成功了。 :::

class Solution {
  public boolean canJump(int[] nums) {
      int n = nums.length;
      int rightmost = 0;
      for (int i = 0; i < n; ++i) {
          if (i <= rightmost) {
              rightmost = Math.max(rightmost, i + nums[i]);
              if (rightmost >= n - 1) {
                  return true;
              }
          } else {
              return false;
          }
      }
      return false;
  }
}

跳跃游戏 II

法1 记忆化搜索 :::warning 用数组 int[] memo 记录搜索过的值
-1 初始化
dfs(idx) == 1 表示 idx 是否能到达尾部。
能到达尾部的前提是 最后一个节点 前面有元素能到达尾部
具体而言即 i + nums[i] >= idx && dfs(i) == 1 :::

class Solution {
  int[] memo;
  public int jump(int[] nums){
      memo=new int[nums.length];
      Arrays.fill(memo, -1);
      return dfs(nums, 0);
  }
  //[idx,nums.length-1]的最小值
  private int dfs(int[] nums,int idx){
      if (idx >= nums.length - 1){
          return 0;
      }
      if (memo[idx] != -1){
          return memo[idx];
      }
      int res= 100000;
      for (int i = 1; i <= nums[idx]; i++){
          res = Math.min(res, 1 + dfs(nums, idx + i));
      }
      return memo[idx] = res;
  }
}

法2 贪心

动态规划-记忆化搜索 - 图1

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        //以当前跳跃步数，能到的最远位置，
        //比如: jump=1跳一次时，最远能到下标currJumpMax=2
        int currJumpMax = 0;
        //当前位置能到的最远位置
        int currPostMax = 0;  
        int jump = 0;
        int i = 0;
        while (i < nums.length - 1) { //不需要检查最后一个位置是因为，最后一个位置我们不用跳了已经
            currPostMax = Math.max(currPostMax, i + nums[i]);
            if (i == currJumpMax) { //已经走到了当前跳跃步数的边界，
                jump++; //我们不得不再跳一次
                currJumpMax = currPostMax; //并记录当前跳跃步数能到的最远位置
            }
            i++;
        }
        return jump;
    }
}

零钱兑换

法1 记忆化搜索 :::warning 用数组 int[] memo 记录搜索过的值
0 初始化
不断更新最小值 min :::

class Solution {
  int[] memo;
  int amount;
  public int coinChange(int[] coins, int amount) {
      if (amount < 1) {
          return 0;
      }
      memo = new int[amount + 1];
      this.amount = amount;
      return dfs(amount, coins);
  }
  //curAmount 所需的最小硬币数
  int dfs(int curAmount, int[] coins) {
      if (curAmount < 0) {
          return -1;
      }
      if (curAmount == 0) {
          return 0;
      }
      if (memo[curAmount] != 0) {
          return memo[curAmount];
      }
      int min = Integer.MAX_VALUE;
      for (int coin : coins) {
          int cur = dfs(curAmount - coin, coins);
          if (cur >= 0 && cur < min) {
              min = cur + 1;
          }
      }
      if (min == Integer.MAX_VALUE) {
          return memo[curAmount] = -1;
      }
      return memo[curAmount] = min;
  }
}

法2 动态规划

动态规划-记忆化搜索 - 图2

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        int[] dp = new int[amount + 1];
        //dp[amount] = dp[amount - coin] + 1
        Arrays.fill(dp, amount + 1);
        Arrays.sort(coins);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    continue;
                }
                break;
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

零钱兑换 II

法1 记忆化搜索 :::warning 定义 int[][] memo= new int[coins.length][amount + 1] 表示下标 idx 之前的硬币之和为 amount 的组合数量。
可以先排序 amount - coins[i] >= 0 才向下递归，否则后面的硬币都不满足条件，break :::

class Solution {
  int[][] memo;
  public int change(int amount, int[] coins) {
      memo = new int[coins.length][amount + 1];
      for (int[] tmp : memo) {
          Arrays.fill(tmp, -1);
      }
      Arrays.sort(coins);
      return dfs(0, amount, coins);
  }
  int dfs(int idx, int amount ,int[] coins) {
      if (amount == 0) {
          return 1;
      }
      if (amount < 0) {
          return 0;
      }
      if (memo[idx][amount] != -1) {
          return memo[idx][amount];
      }
      int ans = 0;
      for (int i = idx; i < coins.length; i++) {
          if (amount - coins[i] >= 0) {
              ans += dfs(i, amount - coins[i], coins);
          } else {
              break;
          }
      }
      return memo[idx][amount] = ans;
  }
}

法2 完全背包 :::warning 定义 f[i] 为考虑凑成总和为 j 的方案数量。 ::: ```java class Solution {

public int change(int amount, int[] coins) {

  int[] dp = new int[amount + 1];
  dp[0] = 1;
  for (int coin : coins) {
      for (int i = coin; i <= amount; i++) {
          dp[i] += dp[i - coin];
      }
  }
  return dp[amount];

}

<a name="h0hRz"></a>
### [目标和](https://leetcode.cn/problems/target-sum/)

- **法1 记忆化搜索**
:::warning
定义  Map<String, Integer> map = new HashMap();  记录计算过的组合数量。
:::
```java
class Solution {

    public int findTargetSumWays(int[] nums, int target) {

        return dfs(0, 0, target, nums);
    }

    Map<String, Integer> map = new HashMap();

    int dfs(int idx, int curSum, int target, int[] nums) {
        if (idx == nums.length) {
            if (curSum == target) {
                return 1;
            }
            return 0;
        }
        String key = idx + "-"+ curSum;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        //选 + 或 选 - 的总和
        int res =  dfs(idx + 1, curSum + nums[idx], target, nums) + dfs(idx + 1, curSum - nums[idx], target, nums);
        map.put(key, res);
        return res;
    }

}

法2 选与不选 :::warning 向下递归，选择+或-分支，直到叶子节点，判断值是否与 target 相等。 ::: ```java class Solution {

int res = 0;

public int findTargetSumWays(int[] nums, int target) {
```
  dfs(0, 0, target, nums);
  return res;
```
}

void dfs(int idx, int curSum, int target, int[] nums) {
```
  if (idx == nums.length) {
      if (curSum == target) {
          res++;
      }
      return;
  }
  //选 +
  dfs(idx + 1, curSum + nums[idx], target, nums);
  //选 -
  dfs(idx + 1, curSum - nums[idx], target, nums);
```
}

}

<a name="DJYpc"></a>
### [最小路径和](https://leetcode.cn/problems/minimum-path-sum/)

- **法1 记忆化搜索**
:::warning
memo[row][col] 记录从 grid[row][col] 到 右下角的最短路径<br />dfs(row, col)   == 从 grid[row][col] 到 右下角的最短路径<br />memo[row][col] = Math.min(l, r) + grid[row][col];
:::
```java
class Solution {

    int[][] memo;

    public int minPathSum(int[][] grid) {
        int rowLen = grid.length;
        int colLen = grid[0].length;
        memo = new int[rowLen][colLen];
        for (int[] m : memo) {
            Arrays.fill(m, -1);
        }
        return dfs(0, 0, grid);
    }

    int dfs(int row, int col, int[][] grid) {
        //数组越界
        if (row >= grid.length || col >= grid[0].length) {
            return Integer.MAX_VALUE;
        }
        if (memo[row][col] != -1) {
            return memo[row][col];
        }
        if(row == grid.length - 1 && col == grid[0].length - 1){
            return grid[row][col];
        }
        int l = dfs(row + 1, col, grid);
        int r = dfs(row, col + 1, grid);
        memo[row][col] = Math.min(l, r) + grid[row][col];
        return memo[row][col];
    }

}

法2 动态规划 :::warning 状态方程：
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); ::: ```java class Solution {

public int minPathSum(int[][] grid) {

  int rowLen = grid.length;
  int colLen = grid[0].length;
  for (int i = 1; i < rowLen; i++) {
      grid[i][0] += grid[i - 1][0];
  }
  for (int i = 1; i < colLen; i++) {
      grid[0][i] += grid[0][i - 1];
  }
  for (int i = 1; i < rowLen; i++) {
      for (int j = 1; j < colLen; j++) {
          grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]);
      }
  }
  return grid[rowLen - 1][colLen - 1];

}

<a name="ZxVJq"></a>
### [打家劫舍](https://leetcode.cn/problems/house-robber/)

- **法1 记忆化搜索**
:::warning
int[] memo;  记录从 idx 偷过的最大值<br />int dfs(int idx, int[] nums)  表示从 idx 房子开始，偷到最后一个房子的最大值<br />偷 与 不偷 两种选择
:::
```java
class Solution {

    int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return Math.max(dfs(0, nums), 0);
    }

    //表示从 idx 房子开始，偷到最后一个房子的最大值
    int dfs(int idx, int[] nums) {
        if (idx < 0 || idx >= nums.length) {
            return 0;
        }
        if (memo[idx] != -1) {
            return memo[idx];
        }
        //偷 idx ,则只能偷 idx + 2
        int t1 = dfs(idx + 2, nums) + nums[idx];
        //不偷 idx ,则可从 idx + 1 偷
        int t2 = dfs(idx + 1, nums);
        //两者最大值
        return memo[idx] = Math.max(t1, t2);
    }
}

法2 动态规划 :::warning 动态规划列表 dp ，dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额 ::: ```java class Solution {

public int rob(int[] nums) {

  int[] dp = new int[nums.length + 1];
  dp[0] = 0;
  dp[1] = nums[0];
  for (int i = 1; i < nums.length; i++) {
      dp[i + 1] = Math.max(dp[i], dp[i - 1] + nums[i]);
  }
  return dp[nums.length];

}


- **法3 动态规划-优化空间**
:::warning
我们发现 dp[n]dp[n] 只与 dp[n-1]dp[n−1] 和 dp[n-2]dp[n−2] 有关系，因此我们可以设两个变量 cur和 pre 交替记录，将空间复杂度降到 O(1) 。
:::
```java
class Solution {

    public int rob(int[] nums) {
        int fn = 0, fn_2 = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res = Math.max(fn_2, fn + nums[i]);
            fn = fn_2;
            fn_2 = res;
        }
        return res;
    }
}

打家劫舍 II

法1 记忆化搜索 :::warning 类似 I, 分两种情况
偷 [0, nums.length - 2] 和 [1, nums.length - 1] 两者的最大值 ::: ```java class Solution {

int[][] memo;

public int rob(int[] nums) {

  if (nums.length == 1) {
      return nums[0];
  }
  memo = new int[2][nums.length];
  for (int[] m : memo) {
      Arrays.fill(m, -1);
  }
  int[] nums1 = Arrays.copyOf(nums, nums.length - 1);
  return Math.max(dfs(0, 0, nums1), dfs(1, 1, nums));

}

//表示从 idx 房子开始，偷到最后一个房子的最大值 int dfs(int idx, int flag, int[] nums) {

  if (idx < 0 || idx >= nums.length) {
      return 0;
  }
  if (memo[flag][idx] != -1) {
      return memo[flag][idx];
  }
  //偷 idx ,则只能偷 idx + 2
  int t1 = dfs(idx + 2,flag, nums) + nums[idx];
  //不偷 idx ,则可从 idx + 1 偷
  int t2 = dfs(idx + 1,flag, nums);
  //两者最大值
  return memo[flag][idx] = Math.max(t1, t2);

}

<a name="hEqYN"></a>
### [打家劫舍 III](https://leetcode.cn/problems/house-robber-iii/)

- **法1 记忆化搜索**
:::warning
用 map 记录偷过的节点到 底部的最大值<br />对于节点 root，存在偷与不偷两种状态，递归遍历即可
:::
```java
class Solution {

    Map<TreeNode, Integer> map = new HashMap();

    public int rob(TreeNode root) {
        return dfs(root);
    }

    int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }
        //偷root
        int t1 = root.val;
        if (root.left != null) {
            t1 += (dfs(root.left.left) + dfs(root.left.right));
        }
        if (root.right != null) {
            t1 += (dfs(root.right.left) + dfs(root.right.right));
        }
        //不偷root
        int t2 = 0;
        t2 = dfs(root.left) + dfs(root.right);
        map.put(root, Math.max(t1, t2));
        return Math.max(t1, t2);
    }
}

法2 动态规划 :::warning 抢与不抢两种状态传递下去
定义一个数组长度为2, res[0]表示不抢该节点可获得最大值, res[1]表示抢劫该节点可获得最大值 :::

class Solution {

  public int rob(TreeNode root) {
      int[] ans = dfs(root);
      return Math.max(ans[0], ans[1]);
  }

  //int[] 表示 抢[0] 与 不抢[1] 该节点的最大value
  int[] dfs(TreeNode root) {
      if (root == null) {
          return new int[]{0, 0};
      }
      int[] l = dfs(root.left);
      int[] r = dfs(root.right);
      //抢 root
      int stealRoot = l[1] + r[1] + root.val;
      //不抢 root
      int noRoot = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
      return new int[]{stealRoot, noRoot};
  }
}

不同路径

法1 记忆化搜索 :::warning 用 memo[][] 记录搜索过的节点到右下角 [m - 1][n - 1] 的路径
memo[i][j] = dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
[i][j] 到 [m - 1][n - 1] 的路径 = 右边节点到右下角的路径数 + 下边节点到右下角的路径数 :::

class Solution {

  int[][] memo;

  public int uniquePaths(int m, int n) {
      memo = new int[m][n];
      return dfs(0, 0, m, n);
  }

  int dfs(int i, int j, int m, int n) {
      if (i == m || j == n) {
          return 0;
      }
      if (i == m - 1 && j == n -1) {
          return 1;
      }
      if (memo[i][j] != 0) {
          return memo[i][j];
      }
      memo[i][j] = dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
      return memo[i][j];
  }
}

法2 动态规划 :::warning dp[i][j] 表示到点 [i][j] 的路径数
状态转移方程： dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; ::: ```java class Solution {

public int uniquePaths(int m, int n) {

  int dp[][] = new int[m][n];
  //第一行和第一列路径数 都是 1
  for (int i = 0; i < m; i++) {
      dp[i][0] = 1;
  }
  for (int i = 0; i < n; i++) {
      dp[0][i] = 1;
  }
  for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
  }
  return dp[m - 1][n - 1];

}

<a name="swnQC"></a>
### [不同路径 II](https://leetcode.cn/problems/unique-paths-ii/)

- **法1 记忆化搜索**
:::warning
思路同 不同路径<br />注意判断 [i][j] 是否为障碍物，是 则 不能到达该点 memo[i][j] = 0, 不是 则 继续遍历
:::
```java
class Solution {

    int[][] memo;

    int[][] obstacleGrid;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        memo = new int[obstacleGrid.length][obstacleGrid[0].length];
        return dfs(0, 0);
    }

    int dfs(int i, int j) {
        if (i == memo.length || j == memo[0].length) {
            return 0;
        }
        if (obstacleGrid[i][j] == 1) {
            return memo[i][j] = 0;
        }
        if (i == memo.length - 1 && j == memo[0].length -1) {
            return 1;
        }
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
        return memo[i][j];
    }
}

法2 动态规划 :::warning 思路同不同路径
第一行和第一列路径数都是 1 ,除非遇到障碍物则后面都是 0
继续遍历，遇到障碍物则 dp[i][j] = 0; :::

class Solution {

  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      int m = obstacleGrid.length;
      int n = obstacleGrid[0].length;
      int dp[][] = new int[m][n];
      //第一行和第一列路径数 都是 1 
      //除非遇到 障碍物 则后面都是 0
      for (int i = 0; i < m; i++) {
          if (obstacleGrid[i][0] == 1) {
              break;
          }
          dp[i][0] = 1;
      }
      for (int i = 0; i < n; i++) {
          if (obstacleGrid[0][i] == 1) {
              break;
          }
          dp[0][i] = 1;
      }
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              if (obstacleGrid[i][j] == 1) {
                  continue;
              }
              dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
          }
      }
      return dp[m - 1][n - 1];
  }
}

整数拆分

法1 记忆化搜索

动态规划-记忆化搜索 - 图3 :::warning 一个正整数 n 拆分成两个数，可用枚举所有情况，1+n-1、2+n-2、…、i+(n-i) 、(n-1)+1，比较每种情况相乘的结果即最终的值；对于每种情况：i+(n-i)，比较 (n-i) 和 (n-i) 继续拆分得到值来确定是否拆分。 :::

class Solution {

    int[] memo;

    public int integerBreak(int n) {
        memo = new int[n + 1];
        return dfs(n);
    }

    int dfs(int n) {
        if (n == 1) {
            return 1;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        for (int i = 1; i <= n; i++) {
            memo[n] = Math.max(Math.max(i * dfs(n - i), i * (n - i)) ,memo[n]);
        }
        return memo[n];
    }
}

法2 动态规划 :::warning dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积
1: 将 i 拆分成 j 和 i - j 的和，且 i - j 不再拆分成多个正整数，此时的乘积是 j (i - j)；
2: 将 i 拆分成 j 和 i - j 的和，且 i - j 继续拆分成多个正整数，此时的乘积是 j dp[i - j]； ::: ```java class Solution {

public int integerBreak(int n) {
```
  int[] dp = new int[n + 1];
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
      int curMax = 0;
      for (int j = 1; j < i; j++) {
          curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
      }
      dp[i] = curMax;
  }
  return dp[n];
```
}

}

<a name="zxDY5"></a>
### [小美打音游](https://leetcode.cn/circle/discuss/RaqW2q/)（美团20220312笔试）

- **法1 记忆化搜索**

![deb756dac57da51a3becab5065aaa60.jpg](https://cdn.nlark.com/yuque/0/2022/jpeg/22159495/1657372528927-690d77ff-cc90-4185-9ae8-7ae56c2c60ab.jpeg#clientId=u19ed9355-03ae-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=1420&id=ue1c67391&margin=%5Bobject%20Object%5D&name=deb756dac57da51a3becab5065aaa60.jpg&originHeight=1278&originWidth=1523&originalType=binary&ratio=1&rotation=0&showTitle=false&size=231196&status=done&style=none&taskId=ub0c70398-e49d-40a5-afcd-be054e4a6ba&title=&width=1692.222267050803)
```java
package com.algorithm.实习.美团;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @ClassName Test4
 * @Description 小美打音游
 * @Author bill
 * @Date 2022/7/9 17:31
 * @Version 1.0
 **/
public class Test4 {

    static int[][] memo;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] arr = new int[m];
        for (int i = 0; i < m; i++) {
            arr[i] = scanner.nextInt();
        }
        memo = new int[m][n + 1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        System.out.println(dfs(0, 1, n, arr));
    }

    //第 curTime 秒 开始到 无伤通关所需要的最小能量
    static int dfs(int curTime, int curRoom, int maxRoom, int[] arr) {
        //此时已到最后，不需要能量
        if (curTime == arr.length) {
            return 0;
        }
        if (memo[curTime][curRoom] != -1) {
            return memo[curTime][curRoom];
        }
        int power = 100000;
        //当前 curRoom = arr[curTime] 必须得跳了
        if (curRoom == arr[curTime]) {
            //所有情况
            for (int i = 1; i <= maxRoom; i++) {
                if (curRoom != i) {
                    power = Math.min(dfs(curTime + 1, i, maxRoom, arr) + 1, power);
                }
            }
        } else {
            //不跳
            power = dfs(curTime + 1, curRoom, maxRoom, arr);
        }
        return memo[curTime][curRoom] = power;

    }
}

牛牛走台阶

法1 记忆化搜索 :::warning int[][][] memo　记录检索过的　memo[curStep][prevStep][prevPrevStep]
dfs(int curStep, int prevStep, int prevPrevStep)　表示从　curStep　到最后台阶ｎ的走法 ::: ```java package com.algorithm.实习.真题;

import java.util.Scanner;

/**

@ClassName NiuNiuStep
@Description https://blog.csdn.net/wdxzuishuia/article/details/115054026
@Author bill
@Date 2022/7/9 21:19

@Version 1.0 **/ public class NiuNiuStep {

static int[][][] memo;

static int m, n;

public static void main(String[] args) {

 Scanner scanner = new Scanner(System.in);
 n = scanner.nextInt();
 m = scanner.nextInt();
 memo = new int[n + 1][m + 1][m + 1];
 System.out.println(dfs(0, 0, 0));

}

static int dfs(int curStep, int prevStep, int prevPrevStep) {

 if (curStep >= n) {
     if (curStep == n) {
         return 1;
     }
     return 0;
 }
 if (memo[curStep][prevStep][prevPrevStep] != 0) {
     return memo[curStep][prevStep][prevPrevStep];
 }
 //可跳 1 - m 任意步数
 int ans = 0;
 for (int i = 1; i <= m; i++) {
     if (prevStep == i || prevPrevStep == i) {
         continue;
     }
     ans += dfs(curStep + i, i, prevStep);
 }
 return memo[curStep][prevStep][prevPrevStep] = ans;

} }

<a name="oPU7v"></a>
### [最优打字策略](https://blog.csdn.net/weixin_43451928/article/details/100057953)

- **法1 记忆化搜索**
:::warning
int dfs(int idx, boolean isLower, boolean isCapsLocks) {<br />传递上个状态，包括isLower和isCapsLocks<br />1 按下 shift + 字母 = 2次按键<br />2 按下 CapsLocks + 字母 = 2次按键
:::
```java
package com.algorithm.实习.真题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Scanner;

/**
 * @ClassName BestType
 * @Description TODO
 * @Author bill
 * @Date 2022/7/9 21:40
 * @Version 1.0
 **/
public class BestType {

    static String s;

    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = br.readLine();
        System.out.println(dfs(0, true, false));
    }

    static int dfs(int idx, boolean isLower, boolean isCapsLocks) {
        if (idx == n) {
            return 0;
        }
        int ans = 10000007;
        //小写
        if (Character.isLowerCase(s.charAt(idx))) {
            //上个状态是小写
            if (isLower) {
                //直接按下 字母 = 1次按键
                ans = Math.min(ans, dfs(idx + 1, isLower, isCapsLocks) + 1);
            } else {
                //1 按下 shift + 字母 = 2次按键
                //2 按下 CapsLocks + 字母 = 2次按键
                ans = Math.min(dfs(idx + 1, isLower, !isCapsLocks) + 2, dfs(idx + 1, !isLower, !isCapsLocks) + 2);
            }
        } else {
            //上个状态是小写
            if (isLower) {
                //1 按下 shift + 字母 = 2次按键
                //2 按下 CapsLocks + 字母 = 2次按键
                ans = Math.min(dfs(idx + 1, isLower, !isCapsLocks) + 2, dfs(idx + 1, !isLower, !isCapsLocks) + 2);
            } else {
                //直接按下 字母 = 1次按键
                ans = Math.min(ans, dfs(idx + 1, isLower, isCapsLocks) + 1);
            }
        }
        return ans;
    }
}

01字符串的价值

法1 记忆化搜索 :::warning dfs(int idx, char prevChar, int val)
选与不选当前字符往下递归 ::: ```java package com.algorithm.实习.真题;

import java.util.Scanner;

/**

@ClassName ZICUAN01
@Description TODO
@Author bill
@Date 2022/7/9 23:00

@Version 1.0 **/ public class ZICUAN01 {

static char[] s;

//000001100000 //55 public static void main(String[] args) {

 Scanner sc = new Scanner(System.in);
 s = sc.next().toCharArray();
 System.out.println(dfs(0, s[0], 0));

}

static int dfs(int idx, char prevChar, int val) {

 if (idx == s.length) {
     return 0;
 }
 //当前字符价值
 int curVal = prevChar == s[idx] ? (val + 1) : 1;
 //选当前
 int haveCur = dfs(idx + 1, s[idx], curVal);
 //不选当前
 int noCur = dfs(idx + 1, prevChar, val);
 return Math.max(curVal + haveCur, noCur);

} } ```