暴力递归-记忆化搜索-动态规划（举例）
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
前言
任何一个动态规划都是某一种暴力递归的优化求解，故先从暴力递归开始做，改成记忆化搜索（傻缓存），再到动态规划
提示：以下是本篇文章正文内容，下面案例可供参考
一、例子
给一个数组，例如arr[]={2,3,5,10},2,3,5,10是钱数，给一个aim值，钱数可以任意张，问组成aim值的方法数
二、代码
1.暴力递归
代码如下（示例）：
public static int ways(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim <= 0) {
return 0;
}
return process(arr, 0, aim);
}
//暴力递归
//在arr[index...]之后的钱中任意钱数拿任意张组成rest的方法数
public static int process(int[] arr, int index, int rest) {
//base case
if (rest < 0) {
return 0;
}
//rest>=0
if (index == arr.length) {
return rest == 0 ? 1 : 0;
}
//有rest且有钱币可拿的情况
int ways = 0;
for (int zhang = 0; (rest - arr[index] * zhang) >= 0; zhang++) {
ways += process(arr, index + 1, rest - arr[index] * zhang);
}
return ways;
}2.记忆化搜索（加缓存）
代码如下（示例）：
public static int ways1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim <= 0) {
return 0;
}
int[][] dp = new int[arr.length + 1][aim + 1];
//一开始所有的过程，都没有计算，缓存为-1
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
dp[i][j] = -1;
}
}
return process1(arr, 0, aim, dp);
}
public static int process1(int[] arr, int index, int rest, int[][] dp) {
//如果缓存中有值，直接返回
if (dp[index][rest] != -1) {
return dp[index][rest];
}
//缓存中没值，先加缓存再返回,即在return的时候先加缓存，再返回缓存
//base case
if (rest < 0) {
dp[index][rest] = 0;
return dp[index][rest];
}
//rest>=0
if (index == arr.length) {
dp[index][rest] = rest == 0 ? 1 : 0;
return dp[index][rest];
}
//有rest且有钱币可拿的情况
int ways = 0;
for (int zhang = 0; (rest - arr[index] * zhang) >= 0; zhang++) {
ways += process(arr, index + 1, rest - arr[index] * zhang);
}
dp[index][rest] = ways;
return dp[index][rest];
}时间复杂度为dp的面积数
3.动态规划（精细化搜索方式）
代码如下（示例）：
public static int ways2(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim <= 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;//dp[N][1...aim]第N行其余是0
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <=aim; rest++) {
int ways = 0;
for (int zhang = 0; (rest - arr[index] * zhang) >= 0; zhang++) {
ways += dp[index + 1][rest - arr[index] * zhang];
}
dp[index][rest] = ways;
return dp[index][rest];
}
}
return dp[0][aim];
}若没有枚举，则时间复杂度与记忆化搜索一样为dp的面积数
总结
若没有枚举，直接加缓存就行了，时间复杂度和动态规划一样。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-05-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录