二维动态规划
64. 最小路径和
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
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
1143. 最长公共子序列
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
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
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
int max(int a, int b) {
return a > b ? a : b;
}
// 空间压缩
int longestCommonSubsequence(char *text1, char *text2) {
char *s1, *s2;
// s2为较短
if (strlen(text1)
516. 最长回文子序列
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
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
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
节点数为n高度不大于m的二叉树个数
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 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 = 1; i--) {
// 再枚举行,而且i不需要到达0,i>=1即可
dp3[i] = 0;
for (int k = 0; k
329. 矩阵中的最长递增路径
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 = 0 && j = matrix[i][j]) return 0;
// 比pre更大(不会走回头路)
int max = 0;
for (int k = 0; k 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 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 = 0 && j = matrix[i][j]) return 0;
if (dp[i][j] != -1) return dp[i][j];
// 比pre更大(不会走回头路)
int max = 0;
for (int k = 0; k 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 res) res = temp;
}
}
return res;
}
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net