- 递归转动态规划
- 机器人运动问题
- 递归形式
- 记忆搜索
- 严格表结构
- 飞棋盘
- 递归实现
- 严格表结构
- 纸币组合
- 暴力递归
- 严格表结构
- 枚举的斜率优化
- 纸币组合最小个数问题
- 递归实现
- 严格表结构
- 整数分裂
- 暴力递归
- 记忆化搜索
- 基础动态规划
- 斜率优化
- 纸牌累计分数（序）（动归）
- 递归实现
- 严格表结构
- bob活着
- 递归实现
- 严格表结构
- 真假情况
- 递归
- 动规
- 硬币结合动归
- 能力蛇最大长度问题
- 递归1
- 递归2
- 动归
- 动归的空间压缩
题目：
参数N：1~N个位置
参数S：初始位置
参数E：终点位置
参数K：要走的步数
机器人在E位置要用K步走到S有几种选择
class U {
public static int fun(int N, int E, int S, int K) {
return f(N, E, S, K);
}
private static int f(int N, int cur, int S, int k) {
if (k == 0) return cur == S ? 1 : 0;
if (cur == 1) return f(N, cur + 1, S, k - 1);
if (cur == N) return f(N, cur - 1, S, k - 1);
return f(N, cur - 1, S, k - 1) + f(N, cur + 1, S, k - 1);
}
}
记忆搜索
class U {
private static int[][] arr;
public static int fun(int N, int E, int S, int K) {
arr=new int[K+1][N+1];
for (int[] ints : arr) {
Arrays.fill(ints, -1);
}
return f(N, E, S, K);
}
private static int f(int N, int cur, int S, int k) {
if (arr[k][cur]!=-1) return arr[k][cur];
if (k == 0) {
arr[k][cur]=cur == S ? 1 : 0;
}else if (cur == 1)
arr[k][cur]=f(N, cur + 1, S, k - 1);
else if (cur == N) {
arr[k][cur]=f(N, cur - 1, S, k - 1);
}else {
arr[k][cur]=f(N, cur - 1, S, k - 1) + f(N, cur + 1, S, k - 1);
}
return arr[k][cur];
}
}
严格表结构
- 确定变量以及变量范围
- 标出目标位置，为返回结果
- 递归结束条件（最终结果）
- 确定依赖关系
- 根据依赖按照合适填补的顺序填补
class U {
public static int fun(int N, int E, int S, int K) {
int[][] dp = new int[K + 1][N + 1];//dp[...][0]不用，这样好表示
dp[0][S] = 1;//递归的结束条件就是我们的初始条件
//根据递归依赖和初始条件的关系，推出填充表顺序
for (int i = 1; i < K + 1; i++) {
for (int cur = 1; cur < N + 1; cur++) {
//三种依赖关系
if (cur == 1) dp[i][cur] = dp[i - 1][cur + 1];
else if (cur == N) dp[i][cur] = dp[i - 1][cur - 1];
else dp[i][cur] = dp[i - 1][cur - 1] + dp[i - 1][cur + 1];
}
}
//返回结果
return dp[K][E];
}
public static void main(String[] args) {
System.out.println(fun(4, 1, 3, 4));
}
}
飞棋盘
问题：在像棋盘上给定起始位置问用K步从起始位置到（0，0）有几种选择
递归实现class T{
public static int process(int x, int y, int step) {
if (x < 0 || x > 8 || y < 0 || y > 9) {
return 0;
}
if (step == 0) {
return (x == 0 && y == 0) ? 1 : 0;
}
return process(x - 1, y + 2, step - 1)
+ process(x + 1, y + 2, step - 1)
+ process(x + 2, y + 1, step - 1)
+ process(x + 2, y - 1, step - 1)
+ process(x + 1, y - 2, step - 1)
+ process(x - 1, y - 2, step - 1)
+ process(x - 2, y - 1, step - 1)
+ process(x - 2, y + 1, step - 1);
}
}
严格表结构
class U {
public static int dp(int x, int y, int step) {
if (x < 0 || y < 0 || x > 9 || y > 8) return 0;
int[][][] dp = new int[10][9][step + 1];
dp[0][0][0] = 1;//初始化条件
for (int i = 1; i <= step; i++) {//层
for (int row = 0; row <= 9; row++) {//行列前后无关
for (int col = 0; col <= 8; col++) {
//依赖关系
dp[row][col][i]=getValue(dp, x - 1, y + 2, step - 1);
dp[row][col][i]=getValue(dp, x + 1, y + 2, step - 1);
dp[row][col][i]=getValue(dp, x + 2, y + 1, step - 1);
dp[row][col][i]=getValue(dp, x + 2, y - 1, step - 1);
dp[row][col][i]=getValue(dp, x + 1, y - 2, step - 1);
dp[row][col][i]=getValue(dp, x - 1, y - 2, step - 1);
dp[row][col][i]=getValue(dp, x - 2, y - 1, step - 1);
dp[row][col][i]=getValue(dp, x - 2, y + 1, step - 1);
}
}
}
return dp[x][y][step];
}
public static int getValue(int[][][] dp, int row, int col, int step) {
if (row < 0 || row > 8 || col < 0 || col > 9) {
return 0;
}
return dp[row][col][step];
}
}
纸币组合
问题：给定数组arr，数据为面值种类，组成res的总值，每种面值可以任意使用，问共有多少种组合方式
暴力递归class T {
public static int process(int[] arr, int res) {
return process(arr, 0, res);
}
private static int process(int[] arr, int index, int res) {
//if (res == 0) return 1;两种判断方式不同动规初始有略微不同但是本质同
//if (index == arr.length || res < 0) return 0;
if (index == arr.length ) return res==0?1:0;
int ways = 0;
for (int num = 0; arr[index] * num <= res; num++) {
ways += process(arr, index + 1, res - arr[index] * num);
}
return ways;
}
}
严格表结构
class T {
public static int process(int[] arr, int res) {
int[][] dp = new int[arr.length + 1][res + 1];
// for (int i = 0; i < arr.length; i++) {
// dp[i][0]=1;
// }跟递归结束条件有关
dp[arr.length][0] = 1;
for (int index = arr.length - 1; index >= 0; index--) {
for (int r = 0; r <= res; r++) {
int ways = 0;
for (int num = 0; arr[index] * num <= r; num++) {//这里的范围为 <=r 不是res
ways += dp[index + 1][r - arr[index] * num];
}
dp[index][r] = ways;
}
}
return dp[0][res];
}
}
枚举的斜率优化
class T {
public static int process(int[] arr, int res) {
int[][] dp = new int[arr.length + 1][res + 1];
dp[arr.length][0] = 1;
for (int index = arr.length - 1; index >= 0; index--) {
for (int r = 0; r <= res; r++) {
//存在枚举递进关系，在严格表结构时相当于有重复计算，这里通过观察有某种递进关系（不需要直到本质含义，就是结构问题）
dp[index][r]=dp[index+1][r];
if (r-arr[index]>=0){
dp[index][r]+=dp[index][r-arr[index]];
}
}
}
return dp[0][res];
}
}
纸币组合最小个数问题
题目：给定数组arr，里面的每个值表示一种面值，可随意使用，问组成aim所需要的最小张数，并返回
递归实现 public static int minCoins1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return -1;
}
return process(arr, 0, aim);
}
// 当前考虑的面值是arr[i]，还剩rest的钱需要找零
// 如果返回-1说明自由使用arr[i..N-1]面值的情况下，无论如何也无法找零rest
// 如果返回不是-1，代表自由使用arr[i..N-1]面值的情况下，找零rest需要的最少张数
public static int process(int[] arr, int i, int rest) {
// base case：
// 已经没有面值能够考虑了
// 如果此时剩余的钱为0，返回0张
// 如果此时剩余的钱不是0，返回-1
if (i == arr.length) {
return rest == 0 ? 0 : -1;
}
// 最少张数，初始时为-1，因为还没找到有效解
int res = -1;
// 依次尝试使用当前面值(arr[i])0张、1张、k张，但不能超过rest
for (int k = 0; k * arr[i] <= rest; k++) {
// 使用了k张arr[i]，剩下的钱为rest - k * arr[i]
// 交给剩下的面值去搞定(arr[i+1..N-1])
int next = process(arr, i + 1, rest - k * arr[i]);
if (next != -1) { // 说明这个后续过程有效
res = res == -1 ? next + k : Math.min(res, next + k);
}
}
return res;
}
严格表结构
public static int minCoins2(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return -1;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
// 设置最后一排的值，除了dp[N][0]为0之外，其他都是-1
for (int col = 1; col <= aim; col++) {
dp[N][col] = -1;
}
for (int i = N - 1; i >= 0; i--) { // 从底往上计算每一行
for (int rest = 0; rest <= aim; rest++) { // 每一行都从左往右
dp[i][rest] = -1; // 初始时先设置dp[i][rest]的值无效
if (dp[i + 1][rest] != -1) { // 下面的值如果有效
dp[i][rest] = dp[i + 1][rest]; // dp[i][rest]的值先设置成下面的值
}
// 左边的位置不越界并且有效
if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1) {
if (dp[i][rest] == -1) { // 如果之前下面的值无效
dp[i][rest] = dp[i][rest - arr[i]] + 1;
} else { // 说明下面和左边的值都有效，取最小的
dp[i][rest] = Math.min(dp[i][rest],
dp[i][rest - arr[i]] + 1);
}
}
}
}
return dp[0][aim];
}
整数分裂
暴力递归
public class Main {
public static int ways1(int n) {
if (n < 1) {
return 0;
}
return process(1, n);
}
public static int process(int pre, int rest) {
if (rest == 0) {
return 1;
}
if (pre > rest) {
return 0;
}
int ways = 0;
for (int i = pre; i <= rest; i++) {
ways += process(i, rest - i);
}
return ways;
}
}
记忆化搜索
public class Main {
public static int ways1(int n) {
if (n < 1) {
return 0;
}
int[][] arr = new int[n + 1][n + 1];
for (int[] is : arr) {
Arrays.fill(is, -1);
}
return process(1, n, arr);
}
public static int process(int pre, int rest, int[][] dp) {
if (dp[pre][rest] != -1) {
return dp[pre][rest];
}
if (rest == 0) {
dp[pre][rest] = 1;
return 1;
}
if (pre > rest) {
dp[pre][rest] = 0;
return 0;
}
int ways = 0;
for (int i = pre; i <= rest; i++) {
ways += process(i, rest - i, dp);
}
dp[pre][rest] = ways;
return ways;
}
}
基础动态规划
public class Main {
public static int ways2(int n) {
if (n < 1) {
return 0;
}
int[][] dp = new int[n + 1][n + 1];
for (int pre = 1; pre < dp.length; pre++) {
dp[pre][0] = 1;
}
for (int pre = n; pre > 0; pre--) {
for (int rest = pre; rest <= n; rest++) {
for (int i = pre; i <= rest; i++) {
dp[pre][rest] += dp[i][rest - i];
}
}
}
return dp[1][n];
}
}
斜率优化
- 枚举行为推导
public class Main {
public static int ways3(int n) {
if (n < 1) {
return 0;
}
int[][] dp = new int[n + 1][n + 1];
for (int pre = 1; pre < dp.length; pre++) {
dp[pre][0] = 1;
}
for (int pre = 1; pre < dp.length; pre++) {
dp[pre][pre] = 1;
}
for (int pre = n - 1; pre > 0; pre--) {
for (int rest = pre + 1; rest <= n; rest++) {
dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
}
}
return dp[1][n];
}
}
纸牌累计分数（序）（动归）
递归实现
public static int win(int[] arr) {
return Math.max(f(arr, 0, arr.length - 1), e(arr, 0, arr.length - 1));
}
public static int f(int[] arr, int l, int r) {
if (l == r) return arr[l];
return Math.max(arr[l] + e(arr, l + 1, r), arr[r] + e(arr, l, r - 1));
}
public static int e(int[] arr, int l, int r) {
if (l == r) return 0;
return Math.min(f(arr, l + 1, r), f(arr, l, r - 1));
}
严格表结构
class U {
//斜线填充
public static int dp(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int i = 0; i < arr.length; i++) {
f[i][i] = arr[i];//递归的结束条件就是我们的初始条件
}
int row = 0;
for (int col = 1; col < arr.length; col++) {
for (int i = row, j = col; i < arr.length && j < arr.length; i++, j++) {
//依赖关系
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
}
//竖向填充
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int i = 0; i < arr.length; i++) {
f[i][i] = arr[i];
}
for (int j = 0; j < arr.length; j++) {
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
}
}
bob活着
题目：给定范围横向N，纵向M，从（i，j）开始走K步（只能上下左右走，且概率相同）没有超过给定范围那么就是活着，如果在过程中超过了范围则死了，返回活着的概率。
递归实现class U {
public static String bob1(int N, int M, int i, int j, int K) {
long all = (long) Math.pow(4, K); // 总共有all中情况
long live = process(N, M, i, j, K); //存活情况个数
long gcd = gcd(all, live);//求最大公约数
return (live / gcd) + " / " + (all / gcd);
}
public static long process(int N, int M, int row, int col, int rest) {
if (row < 0 || row >= N || col < 0 || col >= M) {
return 0;
}
if (rest == 0) {
return 1;
}
long live = process(N, M, row - 1, col, rest - 1);
live += process(N, M, row + 1, col, rest - 1);
live += process(N, M, row, col - 1, rest - 1);
live += process(N, M, row, col + 1, rest - 1);
return live;
}
//求最大公约数
public static long gcd(long m, long n) {
return n == 0 ? m : gcd(n, m % n);
}
}
严格表结构
class U {
public static long gcd(long m, long n) {
return n == 0 ? m : gcd(n, m % n);
}
public static String bob2(int N, int M, int i, int j, int K) {
int[][][] dp = new int[N + 2][M + 2][K + 1];
for (int row = 1; row <= N; row++) {//初始化数据
for (int col = 1; col <= M; col++) {
dp[row][col][0] = 1;
}
}
for (int rest = 1; rest <= K; rest++) {
for (int row = 1; row <= N; row++) {
for (int col = 1; col <= M; col++) {
//递归依赖
dp[row][col][rest] = dp[row - 1][col][rest - 1];
dp[row][col][rest] += dp[row + 1][col][rest - 1];
dp[row][col][rest] += dp[row][col - 1][rest - 1];
dp[row][col][rest] += dp[row][col + 1][rest - 1];
}
}
}
long all = (long) Math.pow(4, K);
long live = dp[i + 1][j + 1][K];
long gcd = gcd(all, live);
return (live / gcd) + "/" + (all / gcd);
}
}
真假情况
递归
class Test {
private static boolean isValid(char[] exp) {
if ((exp.length & 1) == 0) {
return false;
}
for (int i = 0; i < exp.length; i = i + 2) {
if ((exp[i] != '1') && (exp[i] != '0')) {
return false;
}
}
for (int i = 1; i < exp.length; i = i + 2) {
if ((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '^')) {
return false;
}
}
return true;
}
public static int num1(String express, boolean desired) {
if (express == null || express.equals("")) {
return 0;
}
char[] exp = express.toCharArray();
if (!isValid(exp)) {
return 0;
}
return p(exp, desired, 0, exp.length - 1);
}
private static int p(char[] exp, boolean desired, int L, int R) {
if (L == R) {
if (exp[L] == '1') {
return desired ? 1 : 0;
} else {
return desired ? 0 : 1;
}
}
int res = 0;
if (desired) {
for (int i = L + 1; i < R; i += 2) {
switch (exp[i]) {
case '&':
res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
break;
case '|':
res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
break;
case '^':
res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
break;
}
}
} else {
for (int i = L + 1; i < R; i += 2) {
switch (exp[i]) {
case '&':
res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
break;
case '|':
res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
break;
case '^':
res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
break;
}
}
}
return res;
}
}
动规
class Test {
public static int num2(String express, boolean desired) {
if (express == null || express.equals("")) {
return 0;
}
char[] exp = express.toCharArray();
if (!isValid(exp)) {
return 0;
}
int[][] t = new int[exp.length][exp.length];
int[][] f = new int[exp.length][exp.length];
t[0][0] = exp[0] == '0' ? 0 : 1;
f[0][0] = exp[0] == '1' ? 0 : 1;
for (int i = 2; i < exp.length; i += 2) {
t[i][i] = exp[i] == '0' ? 0 : 1;
f[i][i] = exp[i] == '1' ? 0 : 1;
for (int j = i - 2; j >= 0; j -= 2) {
for (int k = j; k < i; k += 2) {
if (exp[k + 1] == '&') {
t[j][i] += t[j][k] * t[k + 2][i];
f[j][i] += (f[j][k] + t[j][k]) * f[k + 2][i] + f[j][k] * t[k + 2][i];
} else if (exp[k + 1] == '|') {
t[j][i] += (f[j][k] + t[j][k]) * t[k + 2][i] + t[j][k] * f[k + 2][i];
f[j][i] += f[j][k] * f[k + 2][i];
} else {
t[j][i] += f[j][k] * t[k + 2][i] + t[j][k] * f[k + 2][i];
f[j][i] += f[j][k] * f[k + 2][i] + t[j][k] * t[k + 2][i];
}
}
}
}
return desired ? t[0][t.length - 1] : f[0][f.length - 1];
}
}
硬币结合动归
class MoneyWays {
//主调函数
public static int moneyWays(int[] arbitrary, int[] onlyone, int money) {
if (money < 0) {
return 0;
}
if ((arbitrary == null || arbitrary.length == 0)
&& (onlyone == null || onlyone.length == 0)) {
return money == 0 ? 1 : 0;
}
int[][] dparb = getDpArb(arbitrary, money);
int[][] dpone = getDpOne(onlyone, money);
if (dparb == null) {
return dpone[dpone.length - 1][money];
}
if (dpone == null) {
return dparb[dparb.length - 1][money];
}
int res = 0;
for (int i = 0; i <= money; i++) {
res += dparb[dparb.length - 1][i]
* dpone[dpone.length - 1][money - i];
}
return res;
}
//多个硬币的方法
private static int[][] getDpArb(int[] arr, int money) {
if (arr == null || arr.length == 0) {
return null;
}
int[][] dp = new int[arr.length][money + 1];
for (int i = 0; i < arr.length; i++) {
dp[i][0] = 1;
}
for (int j = 1; arr[0] * j <= money; j++) {
dp[0][arr[0] * j] = 1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= money; j++) {
dp[i][j] = dp[i - 1][j];
dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
}
}
return dp;
}
//一个硬币的情况
private static int[][] getDpOne(int[] arr, int money) {
if (arr == null || arr.length == 0) {
return null;
}
int[][] dp = new int[arr.length][money + 1];
for (int i = 0; i < arr.length; i++) {
dp[i][0] = 1;
}
if (arr[0] <= money) {
dp[0][arr[0]] = 1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= money; j++) {
dp[i][j] = dp[i - 1][j];
dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
}
}
return dp;
}
}
能力蛇最大长度问题
递归1
public class Main {
public static int fun(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0) {
return 0;
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < m.length; i++) {
int ans = fun(m, i, 0, 0, false);
res = Math.max(res, ans);
}
return res;
}
private static int fun(int[][] m, int i, int j, Integer num, boolean falg) {
if (j == m[0].length - 1) {
return falg ? Math.max(num, num+m[i][j]) : Math.max(num + m[i][j], num - m[i][j]);
}
int no = num;
int yes = num;
//只有一行
if (m.length==1) {
if (!falg&& m[i][j] < 0) {
no=fun(m,i,j+1,num-m[i][j],!falg);
}
yes=fun(m, i, j+1, num+m[i][j], falg);
return Math.max(no, yes);
}
if (i == 0) {
if (!falg && m[i][j] < 0) {
no = Math.max(fun(m, i, j + 1, num - m[i][j], !falg), fun(m, i + 1, j + 1, num - m[i][j], !falg));
}
if (num + m[i][j] > 0) {
yes = Math.max(fun(m, i, j + 1, num + m[i][j], falg), fun(m, i + 1, j + 1, num + m[i][j], falg));
}
return Math.max(no, yes);
} else if (i == m.length - 1) {
if (!falg && m[i][j] < 0) {
no = Math.max(fun(m, i-1, j +1 , num - m[i][j], !falg), fun(m, i , j +1, num - m[i][j], !falg));
}
if (num + m[i][j] > 0) {
yes = Math.max(fun(m, i-1, j + 1, num + m[i][j], falg), fun(m, i , j + 1, num + m[i][j], falg));
}
return Math.max(no, yes);
} else {
if (!falg && m[i][j] < 0) {
no = Math.max(fun(m, i, j + 1, num - m[i][j], !falg),
Math.max(fun(m, i + 1, j + 1, num - m[i][j], !falg), fun(m, i-1, j + 1, num - m[i][j], !falg)));
}
if (num + m[i][j] > 0) {
yes = Math.max(fun(m, i + 1, j + 1, num + m[i][j], falg),
Math.max(fun(m, i, j + 1, num, falg), fun(m, i - 1, j + 1, num + m[i][j], falg)));
}
return Math.max(no, yes);
}
}
}
递归2
class Main {
public static int walk1(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < matrix.length; i++) {
int[] ans = process(matrix, i, 0);
res = Math.max(res, Math.max(ans[0], ans[1]));
}
return res;
}
public static int fun(int[][] m) {
int res = Integer.MIN_VALUE;
for (int i = 0; i < m.length; i++) {
int ans = fun(m, i, 0, 0, false);
res = Math.max(res, ans);
}
return res;
}
// 从(i,j)出发一直走到最右侧的旅程中
// 0) 在没有使用过能力的情况下，返回路径最大和
// 1) 在使用过能力的情况下，返回路径最大和
public static int[] process(int[][] m, int i, int j) {
if (j == m[0].length - 1) {
return new int[] { m[i][j], -m[i][j] };
}
int[] restAns = process(m, i, j + 1);
int restUnuse = restAns[0];
int restUse = restAns[1];
if (i - 1 >= 0) {
restAns = process(m, i - 1, j + 1);
restUnuse = Math.max(restUnuse, restAns[0]);
restUse = Math.max(restUse, restAns[1]);
}
if (i + 1 < m.length) {
restAns = process(m, i + 1, j + 1);
restUnuse = Math.max(restUnuse, restAns[0]);
restUse = Math.max(restUse, restAns[1]);
}
int no = m[i][j] + restUnuse;
int yes = Math.max(m[i][j] + restUse, -m[i][j] + restUnuse);
return new int[] { no, yes };
}
}
动归
class Main {
public static int walk2(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int[][][] dp = new int[matrix.length][matrix[0].length][2];
for (int i = 0; i < dp.length; i++) {
dp[i][matrix[0].length - 1][0] = matrix[i][matrix[0].length - 1];
dp[i][matrix[0].length - 1][1] = -matrix[i][matrix[0].length - 1];
}
for (int j = matrix[0].length - 2; j >= 0; j--) {
for (int i = 0; i < matrix.length; i++) {
int restUnuse = dp[i][j + 1][0];
int restUse = dp[i][j + 1][1];
if (i - 1 >= 0) {
restUnuse = Math.max(restUnuse, dp[i - 1][j + 1][0]);
restUse = Math.max(restUse, dp[i - 1][j + 1][1]);
}
if (i + 1 < matrix.length) {
restUnuse = Math.max(restUnuse, dp[i + 1][j + 1][0]);
restUse = Math.max(restUse, dp[i + 1][j + 1][0]);
}
dp[i][j][0] = matrix[i][j] + restUnuse;
dp[i][j][1] = Math.max(matrix[i][j] + restUse, -matrix[i][j] + restUnuse);
}
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < matrix.length; i++) {
res = Math.max(res, Math.max(dp[i][0][0], dp[i][0][1]));
}
return res;
}
}
动归的空间压缩
