[关闭]
@Catyee 2021-08-18T19:17:34.000000Z 字数 11165 阅读 426

动态规划

数据结构与算法

动态规划问题的一般形式就是求最值，既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

动态规划都会存在重叠子问题，重叠子问题的重复计算会导致效率变低，那么思路就是用一个「备忘录」或者「DP table」来存储计算出来的重叠子问题的值，当之后再遇到这个子问题就不用计算了，这是一种空间换时间的解决思路。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。

一、斐波那契数列

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

  1. // 自顶向下
  2. class Solution {
  3.     final Map<Integer, Integer> cache = new HashMap<>(); // 存储重叠子问题的值
  4.     public int fib(int n) {
  5.         if (n <= 1) {
  6.             return n;
  7.         }
  8.         Integer result = cache.get(n);
  9.         if (result == null) {
  10.             result = fib(n - 1) + fib(n - 2);
  11.             cache.put(n, result);
  12.         }
  13.         return result;
  14.     }
  15. }
  17. // 自下而上
  18. class Solution {
  19.     public int fib(int n) {
  20.         if (n <= 1) {
  21.             return n;
  22.         }
  23.         int prepre = 0;
  24.         int pre = 1;
  25.         int current = 1;
  26.         for (int i = 2; i <= n; i++) {
  27.             current = prepre + pre;
  28.             prepre = pre;
  29.             pre = current;
  30.         }
  31.         return current;
  32.     }
  33. }

斐波那契数列的变种问题：爬楼梯：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思考过程：
一次可以爬1个台阶，或者2个台阶，那么爬n阶总共的方式数量就是最后剩一个台阶的方式的数量加上最后剩两个台阶的方式的数量。
写成方程的方式就是
F(n) = F(n - 1) + F(n - 2)
如果只有一个台阶，自然只有一种方式: f(1)=1
如果有两个台阶，有两种方式: f(2)=2
这不就是斐波那契数列嘛。

二、凑零钱问题

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

  1. 输入：coins = [1, 2, 5], amount = 11
  2. 输出：3 
  3. 解释：11 = 5 + 5 + 1
  5. 输入：coins = [1], amount = 0 (一种特例)
  6. 输出：0
  1. // 自顶向下
  2. Map<Integer, Integer> cache = new HashMap<>(); // 存储重叠子问题的值
  3. public int coinChange(int[] coins, int amount) {
  4.     if (amount == 0) {
  5.         return 0;
  6.     }
  7.     Integer val = cache.get(amount);
  8.     if (val != null) {
  9.         return val;
  10.     }
  11.     int min = -1;
  12.     for (int coin : coins) {
  13.         if (coin > amount) {
  14.             continue;
  15.         }
  16.         if (coin == amount) {
  17.             return 1;
  18.         }
  19.         int current = coinChange(coins, amount - coin) + 1;
  20.         if (current <= 0) {
  21.             continue;
  22.         }
  23.         if (min == -1 || current < min) {
  24.             min = current;
  25.         }
  26.     }
  27.     cache.put(amount, min);
  28.     return min;
  29. }
  31. // 自底向上
  32. public int coinChange(int[] coins, int amount) {
  33.     if (amount == 0) {
  34.         return 0;
  35.     }
  36.     return coinChange(coins, amount, new int[amount]);
  37. }
  39. private int coinChange(int[] coins, int amount, int[] cache) {
  40.     for (int i = 1; i <= amount; i++) {
  41.         int val = Integer.MAX_VALUE;
  42.         for (int coin : coins) {
  43.             if (coin > i) {
  44.                 continue;
  45.             }
  46.             if (coin == i) {
  47.                 val = 1;
  48.                 break; // 1一定是最小的所以直接赋值并退出循环
  49.             }
  50.             if (coin < i) {
  51.                 int current = cache[i - coin - 1] + 1;
  52.                 // 由于cache中可能是-1，-1代表没有，加1之后可能为0，所以current要大于0才代表找到了
  53.                 if (current > 0 && current < val) { 
  54.                     val = current;
  55.                 }
  56.             }
  57.         }
  58.         cache[i - 1] = val == Integer.MAX_VALUE ? -1 : val;
  59.     }
  60.     return cache[amount - 1];
  61. }

三、子序列问题

3.1 最长公共子序列[1143]

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

  1. 输入：text1 = "abcde", text2 = "ace" 
  2. 输出：3  
  3. 解释：最长公共子序列是 "ace" ，它的长度为 3 。

对于两个字符串求子序列的问题，一般都是要细化到s1和s2的每个字符，所以都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划思路。
对于这个题我们定义动态规划函数dp[String s1, int i, String s2, int j]，这个函数的含义就是dp[s1, i, s2, j]就是s1[i...]到s2[j...]的最大子序列长度。

原问题要求s1和s2的最长公共子序列可以转换为求dp[s1, 0, s2, 0]；

我们再来看这个函数结束条件：
如果i等于s1的长度或者j等于s2的长度，相当于s1[i...]或者s2[j...]是空串，此时是没有子序列的，所以长度是0

我们再来看状态转移：
如果s1[i]刚好等于s2[j]，那么dp[s1, i, s2, j] = dp[s1, i + 1, s2, j + 1] + 1; 也就是i和j同时移动
如果s1[i]不等于s2[j]，那么dp[s1, i, s2, j] = max(dp[s1, i + 1, s2, j], dp[s1, i, s2, j + 1]) 也就是i和j分别移动

根据dp函数和状态转移的方式，先写出代码：

  1. public int longestCommonSubsequence(String text1, String text2) {
  2.     char[] chars1 = text1.toCharArray();
  3.     char[] chars2 = text2.toCharArray();
  4.     return calculate(chars1, 0, chars2, 0);
  5. }
  7. private int calculate(char[] chars1, int i, char[] chars2, int j) {
  8.     if (i == chars1.length || j == chars2.length) {
  9.         return 0;
  10.     }
  11.     if (chars1[i] == chars2[j]) {
  12.         return calculate(chars1, i + 1, chars2, j + 1) + 1;
  13.     }
  14.     int left = calculate(chars1, i + 1, chars2, j);
  15.     int right = calculate(chars1, i, chars2, j + 1);
  16.     return Math.max(left, right);
  17. }

这样其实已经可以得到正确答案了，但是当字符串长了之后就会超时。我们知道动态规划最大的特点是有重叠子问题，重叠子问题的重复计算会导致效率变低，那么思路就是用一个存储结构存储重叠子问题的值，之后再遇到就不用计算了，是一种空间换时间的解决思路。

那么这个题的重叠子问题是什么呢？当chars1[i] != chars2[j]的情况下，我们要移动i或j，这个‘或’就包含很多重复计算。那么我们用一个存储结构存储计算出来的子问题的值。

  1. public int longestCommonSubsequence(String text1, String text2) {
  2.     char[] chars1 = text1.toCharArray();
  3.     char[] chars2 = text2.toCharArray();
  4.     int[][] dp = new int[chars1.length][chars2.length];
  5.     for (int i = 0; i < chars1.length; i++) {
  6.         for (int j = 0; j < chars2.length; j++) {
  7.             dp[i][j] = -1;
  8.         }
  9.     } // 初始化数组
  10.     return calculate(chars1, 0, chars2, 0, dp);
  11. }
  13. private int calculate(char[] chars1, int i, char[] chars2, int j, in[][] dp) {
  14.     if (i == chars1.length || j == chars2.length) {
  15.         return 0;
  16.     }
  17.     if (dp[i][j] != -1) { // 如果已经计算过当前子问题，直接返回
  18.         return dp[i][j];
  19.     }
  20.     if (chars1[i] == chars2[j]) {
  21.         int val = calculate(chars1, i + 1, chars2, j + 1, dp) + 1;
  22.         dp[i][j] == val; // 记录子问题的值
  23.         return val;
  24.     }
  25.     int left = calculate(chars1, i + 1, chars2, j, dp);
  26.     int right = calculate(chars1, i, chars2, j + 1, dp);
  27.     int val = Math.max(left, right);
  28.     dp[i][j] = val; // 记录子问题的值
  29.     return val;
  30. }

这样这道题就完成了。总结一下步骤：

再看两道相似的题：

3.2 两个字符串的删除操作 [583]

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

  1. 输入: "sea", "eat"
  2. 输出: 2
  3. 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

第一步 定义动态函数
dp[String s1, int i, String s2, int j]
该函数的含义是dp[s1, i, s2, j]代表删除字符将s1[i...]和s2[j...]变为相同的最少步骤

第二步 将原问题用动态函数进行转化
原问题即为求dp[s1, 0, s2, 0]的值

第三步 找出动态函数的结束条件
如果i先等于s1的长度，说明s1比s2先遍历结束，此时相当于s1[i...]为空串，那么s2中j往后的字符都要删除才能变为一样，所以步数是s2的长度减去j
如果j先等于s2的长度，说明s2比s1先遍历结束，此时相当于s2[j...]为空串，那么s1中i往后的字符都要删除，所以步数是s1的长度减去i

第四步 找出状态转移方式
如果s1[i]刚好等于s2[j]，那么不用删除，i和j同时移动，dp[s1, i, s2, j] = dp[s1, i + 1, s2, j + 1]
如果s1[i]不等于s2[j]，那么当前肯定要删一个字符，至于删除哪个字符就要看是移动i还是j，dp[s1, i, s2, j] = min(dp[s1, i + 1, s2, j], dp[s1, i, s2, j + 1]) + 1

第五步 找出重叠子问题在的地方
s1[i]不等于s2[j]的时候，i或者j移动会有重复计算。

第六步 编程实现：

  1. public int minDistance(String word1, String word2) {
  2.     char[] chars1 = word1.toCharArray();
  3.     char[] chars2 = word2.toCharArray();
  4.     int[][] dp = new int[chars1.length][chars2.length];
  5.     for (int i = 0; i < chars1.length; i++) {
  6.         for (int j = 0; j < chars2.length; j++) {
  7.             dp[i][j] = -1;
  8.         }
  9.     }
  10.     return calculate(chars1, 0, chars2, 0, dp);
  11. }
  13. private int calculate(char[] chars1, int i, char[] chars2, int j, int[][] dp) {
  14.     if (i == chars1.length) {
  15.         return chars2.length - j;
  16.     }
  17.     if (j == chars2.length) {
  18.         return chars1.length - i;
  19.     }
  20.     if (dp[i][j] != -1) {
  21.         return dp[i][j];
  22.     }
  23.     if (chars1[i] == chars2[j]) {
  24.         int val = calculate(chars1, i + 1, chars2, j + 1, dp);
  25.         dp[i][j] = val;
  26.         return val;
  27.     }
  28.     int left = calculate(chars1, i + 1, chars2, j, dp);
  29.     int right = calculate(chars1, i, chars2, j + 1, dp);
  30.     int val = Math.min(left, right) + 1;
  31.     dp[i][j] = val;
  32.     return val;
  33. }

3.3 两个字符串的最小ASCII删除和 [712]

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

  1. 输入: s1 = "sea", s2 = "eat"
  2. 输出: 231
  3. 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
  4. 在 "eat" 中删除 "t" 并将 116 加入总和。
  5. 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

第一步 定义动态函数
dp[String s1, int i, String s2, int j]
该函数的含义是dp[s1, i, s2, j]代表删除字符将s1[i...]和s2[j...]变为相同的最少ASCII和

第二步 将原问题用动态函数进行转化
原问题即为求dp[s1, 0, s2, 0]的值

第三步 找出动态函数的结束条件
如果i先等于s1的长度，说明s1比s2先遍历结束，此时相当于s1[i...]为空串，那么s2中j往后的字符都要删除才能变为一样，所以ASCII和为s2剩余字符的ASCII之和
如果j先等于s2的长度，说明s2比s1先遍历结束，此时相当于s2[j...]为空串，那么s1中i往后的字符都要删除，所以ASCII和为s1剩余字符的ASCII之和

第四步 找出状态转移方式
如果s1[i]刚好等于s2[j]，那么不用删除，i和j同时移动，dp[s1, i, s2, j] = dp[s1, i + 1, s2, j + 1]
如果s1[i]不等于s2[j]，那么当前肯定要删一个字符，至于删除哪个字符就要看是移动i还是j，dp[s1, i, s2, j] = min(dp[s1, i + 1, s2, j] + s1[i], dp[s1, i, s2, j + 1] + s2[j])

第五步 找出重叠子问题在的地方
s1[i]不等于s2[j]的时候，i或者j移动会有重复计算。

第六步 编程实现：

  1. public int minimumDeleteSum(String s1, String s2) {
  2.     char[] chars1 = s1.toCharArray();
  3.     char[] chars2 = s2.toCharArray();
  4.     int[][] dp = new int[chars1.length][chars2.length];
  5.     for (int i = 0; i < chars1.length; i++) {
  6.         for (int j = 0; j < chars2.length; j++) {
  7.             dp[i][j] = -1;
  8.         }
  9.     }
  10.     return calculate(chars1, 0, chars2, 0, dp);
  11. }
  13. private int calculate(char[] chars1, int i, char[] chars2, int j, int[][] dp) {
  14.     if (i == chars1.length) {
  15.         int val = 0;
  16.         for (; j < chars2.length; j++) {
  17.             val += chars2[j];
  18.         }
  19.         return val;
  20.     }
  21.     if (j == chars2.length) {
  22.         int val = 0;
  23.         for (; i < chars1.length; i++) {
  24.             val += chars1[i];
  25.         }
  26.         return val;
  27.     }
  28.     if (dp[i][j] != -1) {
  29.         return dp[i][j];
  30.     }
  31.     if (chars1[i] == chars2[j]) {
  32.         int val = calculate(chars1, i + 1, chars2, j + 1, dp);
  33.         dp[i][j] = val;
  34.         return val;
  35.     }
  36.     int left = calculate(chars1, i + 1, chars2, j, dp) + chars1[i];
  37.     int right = calculate(chars1, i, chars2, j + 1, dp) + chars2[j];
  38.     int val = left < right ? left : right;
  39.     dp[i][j] = val;
  40.     return val;
  41. }

3.4 编辑距离 [72]

再来看一个更为复杂的情况。leetcode第72题编辑距离：
给你两个单词word1和word2，请你计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：

  1. 输入：word1 = "horse", word2 = "ros"
  2. 输出：3
  3. 解释：
  4. horse -> rorse (将 'h' 替换为 'r')
  5. rorse -> rose (删除 'r')
  6. rose -> ros (删除 'e')

还是按照步骤来：

第一步 定义动态规划函数
由于依然是两个字符串，所以我们依然定义dp[String s1, int i, String s2, int j]
该函数的含义是dp[s1, i, s2, j]代表使用插入、删除、替换的操作将s1[i...]变为s2[j...]的最少操作数

第二步 将原问题用动态函数进行转化
原问题即为求dp[s1, 0, s2, 0]的值

第三步 找出动态函数的结束条件
如果i先等于s1的长度，说明s1比s2先遍历结束，此时相当于s1[i...]是空串，要把空串变为s2[j...]，那么把s2剩余的字符全部插入就可以了，操作数等于s2剩余的字符数
如果j先等于s2的长度，说明s2比s1先遍历结束，此时相当于s2[j...]是空串，要把一个字符串变为空串，那么把s1剩余的字符全部删除就可以了，操作数等于s1剩余的字符数

第四步 找出动态迁移方式
如果s1[i]刚好等于s2[j]，这两个字符相等，那么不用进行操作，直接移动i和j，所以此时dp[s1, i, s2, j] = dp[s1, i + 1, s2, j + 1]
如果s1[i]不等于s2[j]，那么此时就要对s1进行操作，操作也就是插入、删除、替换中的一种：
如果是替换，替换结束之后s1的长度没有变，而且替换之后s1在i处的字符和s2在j处的字符相同，所以i和j都要往前移动，此时dp[s1, i, s2, j] = dp[s1, i + 1, s2, j + 1] + 1
如果是删除，想象一下删除s1在i处的字符之后，i处新的字符依然不一定和s2在j处的字符相同，但是s1却变短了；当然我们不会真的去删除字符，那么怎么操作就相当于执行了"删除"操作呢？我们把i往前移动了一步，而不移动j，是不是就相当于删除了i位置的字符？所以此时dp[s1, i, s2, j] = dp[s1, i + 1, s2, j] + 1
如果是插入，那么插入的字符必然和s2在j处的字符相同，同时s1变长了，由于插入使得两个字符相同了，所以j一定是要向前移动一步的，此时i如果不移动，是不是就相当于向s1插入了一个字符？所以此时dp[s1, i, s2, j] = dp[s1, i, s2, j + 1] + 1
三种操作已经讲述清楚了，那么到底哪种是操作数最少的呢？不知道，所以三种情况都要计算，计算出来之后比较得到最小值。

第五步 找出重叠子问题在的地方
s1[i]不等于s2[j]的时候，i或者j移动会有重复计算。

第六步 编程实现：

  1. public int minDistance(String word1, String word2) {
  2.     char[] chars1 = word1.toCharArray();
  3.     char[] chars2 = word2.toCharArray();
  4.     int[][] dp = new int[chars1.length][chars2.length];
  5.     for (int i = 0; i < chars1.length; i++) {
  6.         for (int j = 0; j < chars2.length; j++) {
  7.             dp[i][j] = -1;
  8.         }
  9.     }
  10.     return calculate(chars1, 0, chars2, 0, dp);
  11. }
  13. private int calculate(char[] chars1, int i, char[] chars2, int j, int[][] dp) {
  14.     if (i == chars1.length) {
  15.         return chars2.length - j;
  16.     }
  17.     if (j == chars2.length) {
  18.         return chars1.length - i;
  19.     }
  20.     if (dp[i][j] != -1) {
  21.         return dp[i][j];
  22.     }
  23.     if (chars1[i] == chars2[j]) {
  24.         int val = calculate(chars1, i + 1, chars2, j + 1, dp);
  25.         dp[i][j] = val;
  26.         return val;
  27.     }
  28.     int replace = calculate(chars1, i + 1, chars2, j + 1, dp) + 1; // 替换操作
  29.     int val = replace;
  30.     int delete = calculate(chars1, i + 1, chars2, j, dp) + 1; // 删除操作
  31.     if (delete < val) {
  32.         val = delete;
  33.     }
  34.     int insert = calculate(chars1, i, chars2, j + 1, dp) + 1; // 插入操作
  35.     if (insert < val) {
  36.         val = insert;
  37.     }
  38.     dp[i][j] = val;
  39.     return val;
  40. }

四、一个dp的情况

4.1 最长递增子序列

300 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

  1. 输入：nums = [10,9,2,5,3,7,101,18]
  2. 输出：4
  3. 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

第一步 定义动态函数
我们定义dp[i]为以nums[i]结尾的递增子序列的最大长度
比如示例中dp[0]=1,dp[1]=1,dp[2]=1,dp[3]=2

第二步 将原问题用动态函数进行转换
原问题求最长的递增子序列长度，dp数组中记录的是以nums[i]结尾的递增子序列的最长长度，当求出每个dp数组之后，遍历dp数组，求出记录的最大值，就是最终最长递增子序列的长度

第三步 dp函数结束条件
当i等于nums.length-1的时候结束

第四步 找出动态迁移方式
当计算以nums[i]结尾的递增子序列的最大长度的时候，我们只要遍历[0...i]中，找出那些结尾比nums[i]小的序列，这些序列加上nums[i]就可以构成新的序列，这些新序列中长度最长的那个序列的长度就是以nums[i]结尾的最长的递增子序列的长度

第五步 重叠子问题
计算i出的时候要遍历计算[0...i]，不过已经用dp数组保存了[0...i]的值

第六步 编程实现

  1. public int lengthOfLIS(int[] nums) {
  2.     if (nums == null) {
  3.         return 0;
  4.     }
  5.     int[] dp = new int[nums.length];
  6.     Arrays.fill(dp, 1);
  7.     for (int i = 1; i < nums.length; i++) {
  8.         for (int j = 0; j < i; j++) {
  9.             if (nums[j] < nums[i]) {
  10.                 dp[i] = Math.max(dp[i], dp[j] + 1);
  11.             }
  12.         }
  13.     }
  14.     int result = 0;
  15.     for (int current : dp) {
  16.         if (current > result) {
  17.             result = current;
  18.         }
  19.     }
  20.     return result;
  21. }

4.2 最大子数组

4.3

传递信息

LCP 07. 传递信息

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
每轮信息必须需要传递给另一个人，且信息可重复经过同一个人
给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

  1. 输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
  3. 输出：3
  5. 解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

第一步 定义动态函数
定义dp[i, k]为经过k轮传递到人员i的总方案数

第二步 将原问题用动态函数进行转换
原问题求的是经过k轮传递到人员n-1，所以求的是dp[n-1, k]

第三步 找到dp函数结束条件
由于题目中规定了第一个人是编号为0的小A，所以当k=0时候，如果i也为0，那么就认为找到了一种方案，反之如果k=0时i不为0就认为当前方案是不符合要求的， 即dp[i, 0] = i==0 ? 1 : 0;

第四步 找到dp函数迁移方式
dp[i, k]代表第k轮传递到人员i的方案总数，能直接给i传递信息的人员构成一个集合set, 所以方案总数实际上就是第k-1轮能够传递到set集合中人员方案数相加。即dp[i, k] = sum(dp[a in SET, k-1]) SET为能直接传递信息给i的人员的集合

第五步 找到重叠子问题
可能重复计算某一轮传递给人员i的情况

第六步 编程实现

  1. public int numWays(int n, int[][] relation, int k) {
  2.     int[][] dp = new int[n][k+1]; // 注意k的范围
  3.     for (int i = 0; i < n; i++) {
  4.         for (int j = 0; j <= k; j++) {
  5.             dp[i][j] = -1;
  6.         }
  7.     }
  8.     return numWays(n-1, relation, k, dp);
  9. }
  11. public int numWays(int i, int[][] relation, int k, int[][] dp) {
  12.     if (k == 0) {
  13.         return i == 0 ? 1 : 0;
  14.     }
  15.     if (dp[i][k] != -1) {
  16.         return dp[i][k];
  17.     }
  18.     int result = 0;
  19.     for (int[] cu : relation) {
  20.         if (cu[1] == i) {
  21.             result += numWays(cu[0], relation, k - 1, dp);
  22.         }
  23.     }
  24.     dp[i][k] = result;
  25.     return result;
  26. }

最长回文字串

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注