二维动态规划（上）
2024-01-28 18:56 由
Sprinining 发表于
#其他
二维动态规划
int min(int a, int b) {
return a > b ? b : a;
}
// 从(0,0)到(i,j)的最小路径和，只能向右或向下移动
int recursive(int **grid, int i, int j) {
if (i == 0 && j == 0) return grid[0][0];
int up = 0x7fffffff;
int left = 0x7fffffff;
if (i - 1 >= 0) up = recursive(grid, i - 1, j);
if (j - 1 >= 0) left = recursive(grid, i, j - 1);
// 只能从上方或者左侧到当前位置，选则更小的路径和
return grid[i][j] + min(up, left);
}
// 暴力超时
int minPathSum(int **grid, int gridSize, int *gridColSize) {
return recursive(grid, gridSize - 1, (*gridColSize) - 1);
}
int min(int a, int b) {
return a > b ? b : a;
}
int **dp;
// 从(0,0)到(i,j)的最小路径和，只能向右或向下移动
int recursive(int **grid, int i, int j) {
// 之前计算过就返回
if (dp[i][j] != -1) return dp[i][j];
if (i == 0 && j == 0) {
dp[i][j] = grid[0][0];
} else {
int up = 0x7fffffff;
int left = 0x7fffffff;
if (i - 1 >= 0) up = recursive(grid, i - 1, j);
if (j - 1 >= 0) left = recursive(grid, i, j - 1);
// 只能从上方或者左侧到当前位置，选则更小的路径和
dp[i][j] = grid[i][j] + min(up, left);
}
return dp[i][j];
}
// 自顶向下记忆化搜索
int minPathSum(int **grid, int gridSize, int *gridColSize) {
dp = (int **) malloc(sizeof(int *) * gridSize);
for (int i = 0; i < gridSize; ++i) {
dp[i] = (int *) malloc(sizeof(int) * (*gridColSize));
memset(dp[i], -1, sizeof(int) * (*gridColSize));
}
return recursive(grid, gridSize - 1, (*gridColSize) - 1);
}
int min(int a, int b) {
return a > b ? b : a;
}
// 自底向上+空间压缩
int minPathSum(int **grid, int gridSize, int *gridColSize) {
int rowSize = gridSize;
int columnSize = *gridColSize;
// 一行一行保存最小路径和
int dp[columnSize];
dp[0] = grid[0][0];
// 第一行只和左边的一个元素有关
for (int i = 1; i < columnSize; ++i)
dp[i] = dp[i - 1] + grid[0][i];
for (int i = 1; i < rowSize; ++i) {
// 每行的首元素只和上一行同位置元素有关
dp[0] += grid[i][0];
// 其他行的非首元素和当前行左边的元素和上一行的同位置元素有关
for (int j = 1; j < columnSize; ++j)
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
}
return dp[columnSize - 1];
}
int max(int a, int b) {
return a > b ? a : b;
}
// 返回0~i1和0~i2的最长公共子序列长度
int recursive(char *s1, char *s2, int i1, int i2) {
if (i1 < 0 || i2 < 0) return 0;
// 四种可能
int p1 = recursive(s1, s2, i1 - 1, i2 - 1);
int p2 = recursive(s1, s2, i1 - 1, i2);
int p3 = recursive(s1, s2, i1, i2 - 1);
int p4 = s1[i1] == s2[i2] ? (p1 + 1) : 0;
return max(max(p1, p2), max(p3, p4));
}
// 暴力超时
int longestCommonSubsequence(char *text1, char *text2) {
return recursive(text1, text2, strlen(text1) - 1, strlen(text2) - 1);
}
int max(int a, int b) {
return a > b ? a : b;
}
// 返回前缀长为len1和len2的最长公共子序列长度
int recursive(char *s1, char *s2, int len1, int len2) {
if (len1 == 0 || len2 == 0) return 0;
if (s1[len1 - 1] == s2[len2 - 1])
return recursive(s1, s2, len1 - 1, len2 - 1) + 1;
// 优化：省去了recursive(s1, s2, len1 - 1, len2 - 1)，因为范围包括在下面的两个范围内了
return max(recursive(s1, s2, len1 - 1, len2), recursive(s1, s2, len1, len2 - 1));
}
// 暴力超时
int longestCommonSubsequence(char *text1, char *text2) {
return recursive(text1, text2, strlen(text1), strlen(text2));
}
int max(int a, int b) {
return a > b ? a : b;
}
int **dp;
int length1;
int length2;
// 返回前缀长为len1和len2的最长公共子序列长度
int recursive(char *s1, char *s2, int len1, int len2) {
if (len1 == 0 || len2 == 0) return 0;
if (dp[len1][len2] != -1) return dp[len1][len2];
if (s1[len1 - 1] == s2[len2 - 1]) {
dp[len1][len2] = recursive(s1, s2, len1 - 1, len2 - 1) + 1;
} else {
// 优化：省去了recursive(s1, s2, len1 - 1, len2 - 1)，因为范围包括在下面的两个范围内了
dp[len1][len2] = max(recursive(s1, s2, len1 - 1, len2), recursive(s1, s2, len1, len2 - 1));
}
return dp[len1][len2];
}
// 自顶向下记忆化搜索
int longestCommonSubsequence(char *text1, char *text2) {
length1 = strlen(text1);
length2 = strlen(text2);
dp = (int **) malloc(sizeof(int *) * (length1 + 1));
for (int i = 0; i <= length1; ++i) {
dp[i] = (int *) malloc(sizeof(int) * (length2 + 1));
memset(dp[i], -1, sizeof(int) * (length2 + 1));
}
return recursive(text1, text2, length1, length2);
}
int max(int a, int b) {
return a > b ? a : b;
}
// 自底向上
int longestCommonSubsequence(char *text1, char *text2) {
int length1 = strlen(text1);
int length2 = strlen(text2);
int dp[length1 + 1][length2 + 1];
// 第一行和第一列都是0
for (int i = 0; i <= length1; ++i) dp[i][0] = 0;
for (int i = 0; i <= length2; ++i) dp[0][i] = 0;
// 和左边，上边，左上角的元素有关
for (int len1 = 1; len1 <= length1; ++len1) {
for (int len2 = 1; len2 <= length2; ++len2) {
if (text1[len1 - 1] == text2[len2 - 1])
dp[len1][len2] = dp[len1 - 1][len2 - 1] + 1;
else
dp[len1][len2] = max(dp[len1 - 1][len2], dp[len1][len2 - 1]);
}
}
return dp[length1][length2];
}
int max(int a, int b) {
return a > b ? a : b;
}
// 空间压缩
int longestCommonSubsequence(char *text1, char *text2) {
char *s1, *s2;
// s2为较短
if (strlen(text1) < strlen(text2)) {
s1 = text2;
s2 = text1;
} else {
s1 = text1;
s2 = text2;
}
int length1 = strlen(s1);
int length2 = strlen(s2);
// 长度较短但滚动次数较多的数组，
int dp[length2 + 1];
// 第0行全0
memset(dp, 0, sizeof(int) * (length2 + 1));
for (int len1 = 1; len1 <= length1; ++len1) {
// 左上角元素
int leftUp = dp[0];
// 修改前暂存当前元素
int temp;
for (int len2 = 1; len2 <= length2; ++len2) {
temp = dp[len2];
if (s1[len1 - 1] == s2[len2 - 1])
// 与左上角有关
dp[len2] = leftUp + 1;
else
// 与左边和上边的最大值有关
dp[len2] = max(dp[len2 - 1], dp[len2]);
leftUp = temp;
}
}
return dp[length2];
}
int max(int a, int b) {
return a > b ? a : b;
}
// 返回下标left~right的最长回文子序列长度
int recursive(char *s, int left, int right) {
// if (left > right) return 0;
// 只有一个元素
if (left == right) return 1;
// 只有两个元素
if (left + 1 == right) return s[left] == s[right] ? 2 : 1;
if (s[left] == s[right]) {
return recursive(s, left + 1, right - 1) + 2;
} else {
return max(recursive(s, left, right - 1), recursive(s, left + 1, right));
}
}
// 暴力超时
int longestPalindromeSubseq(char *s) {
return recursive(s, 0, strlen(s) - 1);
}
int max(int a, int b) {
return a > b ? a : b;
}
int **dp;
int len;
// 返回下标left~right的最长回文子序列长度
int recursive(char *s, int left, int right) {
// 只有一个元素
if (left == right) return 1;
// 只有两个元素
if (left + 1 == right) {
dp[left][right] = s[left] == s[right] ? 2 : 1;
}
// 已经有记录就返回
if (dp[left][right] != -1) return dp[left][right];
if (s[left] == s[right]) {
dp[left][right] = recursive(s, left + 1, right - 1) + 2;
} else {
dp[left][right] = max(recursive(s, left, right - 1), recursive(s, left + 1, right));
}
return dp[left][right];
}
// 自顶向下记忆化搜索
int longestPalindromeSubseq(char *s) {
len = strlen(s);
// dp[i][j]表示从i到j位置的最长回文子序列长度
dp = (int **) malloc(sizeof(int *) * len);
for (int i = 0; i < len; ++i) {
dp[i] = (int *) malloc(sizeof(int) * len);
memset(dp[i], -1, sizeof(int) * len);
}
// 主对角线为1，只需再填写上三角矩阵
for (int i = 0; i < len; ++i) dp[i][i] = 1;
return recursive(s, 0, len - 1);
}
int max(int a, int b) {
return a > b ? a : b;
}
// 自底向上
int longestPalindromeSubseq(char *s) {
int len = strlen(s);
// dp[i][j]表示从i到j位置的最长回文子序列长度
int dp[len][len];
for (int left = len - 1; left >= 0; left--) {
// 主对角线为1，只需再填写上三角矩阵
dp[left][left] = 1;
// 主对角线上方的一条斜线
if (left + 1 < len)
dp[left][left + 1] = s[left] == s[left + 1] ? 2 : 1;
// 上三角的其他位置，之和左边、下边、左下角相关
for (int right = left + 2; right < len; ++right) {
if (s[left] == s[right])
dp[left][right] = dp[left + 1][right - 1] + 2;
else
dp[left][right] = max(dp[left + 1][right], dp[left][right - 1]);
}
}
return dp[0][len - 1];
}
int max(int a, int b) {
return a > b ? a : b;
}
// 空间压缩
int longestPalindromeSubseq(char *s) {
int len = strlen(s);
int dp[len];
// 左下角元素
int leftDown;
for (int left = len - 1; left >= 0; left--) {
// dp[left][left]
dp[left] = 1;
// 主对角线上方的一条斜线
if (left + 1 < len) {
// 记录下左下角
leftDown = dp[left + 1];
// dp[left][left+1]
dp[left + 1] = s[left] == s[left + 1] ? 2 : 1;
}
// 上三角的其他位置，之和左边、下边、左下角相关
for (int right = left + 2; right < len; ++right) {
int backup = dp[right];
if (s[left] == s[right])
dp[right] = leftDown + 2;
else
// 没更新前，dp[right]表示dp[left+1][right]，dp[right-1]表示dp[left][right-1]
dp[right] = max(dp[right], dp[right - 1]);
leftDown = backup;
}
}
return dp[len - 1];
}
package class067;
// 节点数为n高度不大于m的二叉树个数
// 现在有n个节点，计算出有多少个不同结构的二叉树
// 满足节点个数为n且树的高度不超过m的方案
// 因为答案很大，所以答案需要模上1000000007后输出
// 测试链接 : https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code05_NodenHeightNotLargerThanm {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
out.println(compute3(n, m));
}
out.flush();
out.close();
br.close();
}
public static int MAXN = 51;
public static int MOD = 1000000007;
// 记忆化搜索
public static long[][] dp1 = new long[MAXN][MAXN];
static {
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
dp1[i][j] = -1;
}
}
}
// 二叉树节点数为n
// 高度不能超过m
// 结构数返回
// 记忆化搜索
public static int compute1(int n, int m) {
if (n == 0) {
return 1;
}
// n > 0
if (m == 0) {
return 0;
}
if (dp1[n][m] != -1) {
return (int) dp1[n][m];
}
long ans = 0;
// n个点，头占掉1个
for (int k = 0; k < n; k++) {
// 一共n个节点，头节点已经占用了1个名额
// 如果左树占用k个，那么右树就占用i-k-1个
ans = (ans + ((long) compute1(k, m - 1) * compute1(n - k - 1, m - 1)) % MOD) % MOD;
}
dp1[n][m] = ans;
return (int) ans;
}
// 严格位置依赖的动态规划
public static long[][] dp2 = new long[MAXN][MAXN];
public static int compute2(int n, int m) {
for (int j = 0; j <= m; j++) {
dp2[0][j] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp2[i][j] = 0;
for (int k = 0; k < i; k++) {
// 一共i个节点，头节点已经占用了1个名额
// 如果左树占用k个，那么右树就占用i-k-1个
dp2[i][j] = (dp2[i][j] + dp2[k][j - 1] * dp2[i - k - 1][j - 1] % MOD) % MOD;
}
}
}
return (int) dp2[n][m];
}
// 空间压缩
public static long[] dp3 = new long[MAXN];
public static int compute3(int n, int m) {
dp3[0] = 1;
for (int i = 1; i <= n; i++) {
dp3[i] = 0;
}
for (int j = 1; j <= m; j++) {
// 根据依赖，一定要先枚举列
for (int i = n; i >= 1; i--) {
// 再枚举行，而且i不需要到达0，i>=1即可
dp3[i] = 0;
for (int k = 0; k < i; k++) {
// 枚举
dp3[i] = (dp3[i] + dp3[k] * dp3[i - k - 1] % MOD) % MOD;
}
}
}
return (int) dp3[n];
}
}
int rowSize;
int columnSize;
int directions[4][2] = {{-1, 0},
{1, 0},
{0, -1},
{0, 1}};
bool isPositionLegal(int i, int j) {
return i >= 0 && i < rowSize && j >= 0 && j < columnSize;
}
// 从matrix[i, j]出发，能走出来的最长递增路径长度
int recursive(int **matrix, int i, int j, int pre) {
if (pre >= matrix[i][j]) return 0;
// 比pre更大（不会走回头路）
int max = 0;
for (int k = 0; k < 4; ++k) {
int nextI = i + directions[k][0];
int nextJ = j + directions[k][1];
// 没越界
if (isPositionLegal(nextI, nextJ)) {
int temp = recursive(matrix, nextI, nextJ, matrix[i][j]);
if (temp > max) max = temp;
}
}
return max + 1;
}
// 暴力超时
int longestIncreasingPath(int **matrix, int matrixSize, int *matrixColSize) {
rowSize = matrixSize;
columnSize = *matrixColSize;
int res = 0;
for (int i = 0; i < rowSize; ++i) {
for (int j = 0; j < columnSize; ++j) {
int temp = recursive(matrix, i, j, -1);
if (temp > res) res = temp;
}
}
return res;
}
int rowSize;
int columnSize;
int directions[4][2] = {{-1, 0},
{1, 0},
{0, -1},
{0, 1}};
int **dp;
bool isPositionLegal(int i, int j) {
return i >= 0 && i < rowSize && j >= 0 && j < columnSize;
}
// 从matrix[i, j]出发，能走出来的最长递增路径长度
int recursive(int **matrix, int i, int j, int pre) {
if (pre >= matrix[i][j]) return 0;
if (dp[i][j] != -1) return dp[i][j];
// 比pre更大（不会走回头路）
int max = 0;
for (int k = 0; k < 4; ++k) {
int nextI = i + directions[k][0];
int nextJ = j + directions[k][1];
// 没越界
if (isPositionLegal(nextI, nextJ)) {
int temp = recursive(matrix, nextI, nextJ, matrix[i][j]);
if (temp > max) max = temp;
}
}
dp[i][j] = max + 1;
return dp[i][j];
}
// 记忆化搜索
int longestIncreasingPath(int **matrix, int matrixSize, int *matrixColSize) {
rowSize = matrixSize;
columnSize = *matrixColSize;
dp = (int **) malloc(sizeof(int *) * rowSize);
for (int i = 0; i < rowSize; ++i) {
dp[i] = (int *) malloc(sizeof(int) * columnSize);
memset(dp[i], -1, sizeof(int) * columnSize);
}
int res = 0;
for (int i = 0; i < rowSize; ++i) {
for (int j = 0; j < columnSize; ++j) {
int temp = recursive(matrix, i, j, -1);
if (temp > res) res = temp;
}
}
return res;
}
热门相关：墨桑 都市狐仙养成记 都市天使 3分钟合作伙伴 姐妹的邻居