数字三角形
-
数字三角形 - 蓝桥云课 (lanqiao.cn)
动态规划的典型解题方法就是寻找子问题，之后确定dp数组的定义以及递推公式。
- 确定dp数组以及下标含义：dp[i][j]表示走到三角形的下标为i，j的位置时，最大的和。
- dp数组初始化：dp[0][0]是多少？在三角形顶，最大值自然就是path[0][0]。
- 确定递推公式：dp[i][j]由两个状态推导而来，分别是正上方和左上方。由于取最大值，就找这两个值中最大的就好。
- 确定遍历顺序：从上往下，从左往右遍历，注意，本题在遍历过程中没有更新停在i , j位置时的值。也正是这个原因，我们初始化也放到遍历之后。
- 本题还有一个特殊点，就是往左走和往右走的步数不能超过1，这里可以使用一个技巧，就是最后一定停在中间！
import java.util.*;
public class Main {
static int N ,lpath , rpath;
static int [][] path;
static int [] dx = new int []{-1 , -1};
static int [] dy = new int []{-1 , 0};
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt();
path = new int[N][N];
for(int i = 0 ; i < N ; i ++){
for(int j = 0 ; j <= i ; j ++){
path[i][j] = s.nextInt();
}
}
//dp定义：走到path[i][j]时的最大和
//走的次数怎么表示？
int [][] dp = new int [N][N];
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j <= i ; j ++){
int max = Integer.MIN_VALUE;
//分别尝试两种走法
for(int k = 0 ; k < 2 ; k ++){
int x = i + dx[k];
int y = j + dy[k];
if(x >= 0 && y >= 0 && y <= i){
max = Math.max(dp[x][y] , max);
}
}
if(i == 0 && j == 0) dp[0][0] = path[0][0] ; else dp[i][j] = max + path[i][j];
}
}
if(N % 2 != 0){
System.out.println(dp[N - 1][N / 2]);
}else{
System.out.println(Math.max(dp[N - 1][N / 2 - 1] , dp[N - 1][N / 2]));
}
}
}
包子凑数
本涉及到数论和动态规划两个层面：
数论：两个数的最大公因数不是1（不为互质），说明可能最大公因数是奇数/偶数，那么就凑不出来偶数或奇数，（最大公因数是奇数，凑不出偶数，反之成立）凑不出来的个数是无限个。
动态规划：如果能凑出j，那么一定能凑出j + num[i]，即为找到重叠子问题。也找到了递推公式推导方法。
public class Main {
static int N , sum; //n种蒸笼
static int [] num; //第i个蒸笼可以放nums[i]个包子
static boolean [] dp = new boolean[10001]; //表示是否能凑出i。
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt();
num = new int[N + 1];
for(int i = 1 ; i <= N ; i ++){
num[i] = s.nextInt();
dp[num[i]] = true;
}
//4能被2整除，那么2就是4的约数（因数）。
int yueshu = num[1];
for(int i = 1 ; i <= N - 1 ; i ++){
yueshu = yue(yueshu,num[i + 1]);
}
//如果不为互质数，说明答案无限。两个数互相的因数为1就是互为质数。
if(yueshu != 1){
System.out.println("INF");
return;
}
//递推公式：如果能凑出j，那么一定能凑出j + num[i]
for(int i = 1 ; i <= N ; i ++){
for(int j = 1; j < 10001 ; j ++){
if(dp[j] && j + num[i] <= 10000){
dp[j + num[i]] = true;
}
}
}
for(boolean b : dp){
if(!b){
sum ++;
}
}
System.out.println(sum - 1);
}
//找到最大公约数
static int yue(int a , int b){
if(b == 0){
return a;
}
return yue(b , a% b);
}
}
摆动序列
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。
小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。
- 确定dp数组以及下标含义：
dp[i][j]：i为奇数，表示序列长度为i时，第i个数大于j的选择总数。
i为偶数，表示序列长度为i时，第i个数小于j的选择总数。 - 递推公式：在注释中已经写出。
- 遍历顺序：以i为偶数项为例。寻找一个数小于另一个数的数量，就要先找到这个数字小于更大数的数量。也就是：
dp[i][j] = (dp[i - 1][j + 1] + dp[i][j + 1])。因为 j 是j + 1推导而来，所以需要倒序遍历。 - dp数组初始化：第一行没有限制，我们可以随意选择第一个数，即只能走一条路线。
public class Main {
static int m; // 摆动序列的长度
static int n; //每个数的范围1-n
static int [][] dp;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
m = s.nextInt();
n = s.nextInt();
//当i为奇数，dp[i][j]表示长度为i时，第i个数大于j的选择总数
//当i为偶数时，dp[i][j]表示第i个数小于j的选择总数
dp = new int [m + 1][n + 2];
for(int j = 1 ; j <= n ; j ++) dp[1][j] = 1;
for(int i = 2 ; i <= m ; i ++){
//当i为偶数
if(i % 2 == 0){
//计算第i个数小于j的个数—>第i - 1个数小于更大的数（j + 1）的个数 + 第i个数小于j + 1的个数。
for(int j = n ; j >= 1 ; j --) dp[i][j] = (dp[i - 1][j + 1] + dp[i][j + 1]) % 10000;
}else{
//第i个数大于j - 1的个数 + 第i - 1个数大于j - 1的个数。
for(int j = 1; j <= n ; j ++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % 10000;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = (ans + dp[m][i]) % 10000;
System.out.print(ans);
}
}