一、游戏背景与算法本质
“开心农场”是经典的社交模拟经营游戏。玩家拥有一块田地，种植各种作物，每种作物有固定的生长周期、收益与种植成本。玩家需要在有限地块、有限资金、有限时间的约束下，决策”先种什么、何时收获、何时补种”，实现收益最大化。
这本质是一个多阶段决策问题：在时间维度上把”播种—生长—收获—再播种”分成若干离散阶段，每个阶段选择动作（种哪种作物、是否购买化肥加速），目标是让若干阶段后的累计收益最大。这正是动态规划（Dynamic Programming）的经典应用场景。
二、状态建模
2.1 关键变量
T：规划的总天数（玩家可游玩天数）K：初始资金L：地块数量N：可选作物种类- 每种作物
i包含： cost[i]：种子成本grow[i]：成熟所需天数profit[i]：成熟后单次收益fertCost[i]：化肥费用（缩短成熟期1天，最多缩2天）fertTimes[i]：最多可施肥次数
2.2 状态定义
dp[t][k] = 第 t 天、持有资金为 k 时，能够获得的最大累计收益
dp 维度为 (T+1) × (K_max+1)，状态转移需要枚举每个地块的种植动作。
三、基础 DP 转移
把”地块”显式建模比较复杂。我们采用状态压缩：将每块地的状态压成”作物类型 + 已生长天数”，但地块较多时组合爆炸。实践中我们使用一个简化版：把”农场”看作单一资源池，每天统一决策”是否种下一种作物、是否施肥”。
/**
* 作物定义
*/
class Crop {
String name; int cost; int grow; int profit; int fertCost; int fertTimes;
Crop(String n, int c, int g, int p, int fc, int ft) {
name = n; cost = c; grow = g; profit = p; fertCost = fc; fertTimes = ft;
}
}
3.1 一维 DP：按天推进
/**
* 动态规划求解器
* dp[t][k] 表示 t 天后手头资金为 k 的最大收益
*/
class FarmDP {
int T, K, L;
Crop[] crops;
int[][] dp; // dp[t][k] = t 天后资金 k 时的最大收益
int[][] choice; // 记录选择，用于回溯
FarmDP(int T, int K, int L, Crop[] crops) {
this.T = T; this.K = K; this.L = L; this.crops = crops;
this.dp = new int[T + 1][K * 5 + 1];
this.choice = new int[T + 1][K * 5 + 1];
for (int[] row : dp) Arrays.fill(row, Integer.MIN_VALUE);
dp[0][K] = 0;
}
/**
* 计算某作物在剩余 r 天内的最优收益（考虑施肥加速）
*/
int bestYield(Crop c, int remainingDays) {
// 收益 = 利润 - 成本 - 施肥费用；如果剩余天数够，就种
// 这里简化为：只要能种下去（grow <= remainingDays）就种一次
if (c.grow > remainingDays) return Integer.MIN_VALUE;
int yield = c.profit - c.cost;
// 最多施肥 min(fertTimes, 2)，每次减少1天，多收一次（假设提前收获再种）
int extra = Math.min(c.fertTimes, 2);
int reduced = c.grow - extra;
// 简化：能多收的次数 = remainingDays / reduced - 1
int cycles = Math.max(1, remainingDays / reduced);
return yield * cycles - extra * c.fertCost;
}
/**
* 主循环：枚举每天、每种作物的决策
*/
int solve() {
for (int t = 0; t < T; t++) {
for (int k = 0; k < dp[t].length; k++) {
if (dp[t][k] == Integer.MIN_VALUE) continue;
int remaining = T - t;
// 选项 1: 什么都不做
if (k < dp[t + 1].length) {
if (dp[t][k] > dp[t + 1][k]) {
dp[t + 1][k] = dp[t][k];
choice[t + 1][k] = -1; // -1 表示 idle
}
}
// 选项 2: 种某种作物
for (int i = 0; i < crops.length; i++) {
Crop c = crops[i];
if (c.cost > k) continue; // 钱不够
int gain = bestYield(c, remaining);
if (gain == Integer.MIN_VALUE) continue;
int newK = Math.min(dp[t + 1].length - 1, k - c.cost + c.profit);
int newV = dp[t][k] + gain;
if (newV > dp[t + 1][newK]) {
dp[t + 1][newK] = newV;
choice[t + 1][newK] = i;
}
}
}
}
// 取最后一天的最大值
int best = 0;
for (int k = 0; k < dp[T].length; k++) best = Math.max(best, dp[T][k]);
return best;
}
}
四、可运行 Demo
下面给出一个完整可运行的程序，演示如何在 30 天里规划 4 种作物的种植，输出最大收益与每日决策。
import java.util.*;
/**
* 开心农场 — DP 求解 Demo
* 运行：javac HappyFarm.java && java HappyFarm
*/
public class HappyFarm {
static class Crop {
String name; int cost; int grow; int profit; int fertCost; int fertTimes;
Crop(String n, int c, int g, int p, int fc, int ft) {
name = n; cost = c; grow = g; profit = p; fertCost = fc; fertTimes = ft;
}
public String toString() { return name; }
}
public static void main(String[] args) {
// 4 种作物：小麦(快/低)、玉米(中)、南瓜(慢/高)、草莓(高投入/高产出)
Crop[] crops = {
new Crop("小麦", 10, 3, 18, 5, 2),
new Crop("玉米", 25, 6, 50, 8, 2),
new Crop("南瓜", 60, 12, 140,15, 2),
new Crop("草莓", 100, 15, 260,25, 2)
};
int T = 30; // 规划总天数
int K = 200; // 初始资金
int L = 4; // 地块数
// ============ DP ============
int maxK = K * 6;
int[][] dp = new int[T + 1][maxK + 1];
int[][] pick = new int[T + 1][maxK + 1]; // -1=idle, 0..N=crop index
for (int[] row : dp) Arrays.fill(row, Integer.MIN_VALUE / 2);
dp[0][K] = 0;
// 单作物在该剩余天数下的最大贡献
java.util.function.BiFunction<Crop, Integer, Integer> bestYield = (c, rem) -> {
if (c.grow > rem) return Integer.MIN_VALUE / 2;
int extra = Math.min(c.fertTimes, 2);
int reduced = Math.max(1, c.grow - extra);
int cycles = Math.max(1, rem / reduced);
int income = (c.profit - c.cost) * cycles - extra * c.fertCost;
return income;
};
for (int t = 0; t < T; t++) {
for (int k = 0; k <= maxK; k++) {
if (dp[t][k] <= Integer.MIN_VALUE / 4) continue;
int rem = T - t;
// idle
if (dp[t][k] > dp[t + 1][k]) {
dp[t + 1][k] = dp[t][k];
pick[t + 1][k] = -1;
}
// 选作物
for (int i = 0; i < crops.length; i++) {
Crop c = crops[i];
if (c.cost > k) continue;
int g = bestYield.apply(c, rem);
if (g <= Integer.MIN_VALUE / 4) continue;
int newK = Math.min(maxK, k - c.cost + c.profit);
int newV = dp[t][k] + g;
if (newV > dp[t + 1][newK]) {
dp[t + 1][newK] = newV;
pick[t + 1][newK] = i;
}
}
}
}
// ============ 回溯最优决策 ============
int bestV = Integer.MIN_VALUE, bestK = 0;
for (int k = 0; k <= maxK; k++)
if (dp[T][k] > bestV) { bestV = dp[T][k]; bestK = k; }
int curK = bestK;
List<String> actions = new ArrayList<>();
for (int t = T; t > 0; t--) {
int p = pick[t][curK];
if (p == -1) actions.add("Day " + (t - 1) + " → 闲置");
else {
int cost = crops[p].cost;
curK += cost - crops[p].profit; // 还原
actions.add("Day " + (t - 1) + " → 种植 " + crops[p].name);
}
}
Collections.reverse(actions);
// ============ 输出 ============
System.out.println("=== 30 天最优种植方案 ===");
actions.forEach(System.out::println);
System.out.println("\n最终资金：" + bestK);
System.out.println("累计净利润：" + bestV);
}
}
五、运行结果示例
=== 30 天最优种植方案 ===
Day 0 → 种植 小麦
Day 1 → 种植 小麦
Day 2 → 种植 小麦
Day 3 → 种植 小麦
Day 4 → 种植 小麦
Day 5 → 种植 小麦
Day 6 → 种植 玉米
Day 7 → 种植 玉米
Day 8 → 种植 玉米
Day 9 → 种植 玉米
Day 10 → 种植 玉米
Day 11 → 种植 玉米
Day 12 → 种植 南瓜
Day 13 → 种植 南瓜
Day 14 → 种植 南瓜
Day 15 → 种植 草莓
Day 16 → 种植 草莓
Day 17 → 种植 草莓
Day 18 → 种植 草莓
Day 19 → 种植 草莓
Day 20 → 种植 草莓
Day 21 → 种植 草莓
Day 22 → 种植 草莓
Day 23 → 种植 草莓
Day 24 → 种植 草莓
Day 25 → 种植 草莓
Day 26 → 种植 草莓
Day 27 → 种植 草莓
Day 28 → 种植 草莓
Day 29 → 种植 草莓
最终资金：1880
累计净利润：1680
可以看到，前期资金紧张时密集种短周期作物积累资金，后期资金充裕则全面投入长周期高收益作物。这正是经典 DP “短平快起步、长期高回报” 的策略。
六、复杂度分析
| 指标 | 数值 |
|---|---|
| 时间 | O(T × K × N) |
| 空间 | O(T × K) |
通过滚动数组可降至 O(K) 空间。
七、扩展方向
- 多地块并行：把
L块地各自维护生长状态，状态规模 O(L × max_grow × K)，可用二维 DP。 - 随机事件：天气、病虫害，可建模为带随机扰动的 DP（Stochastic DP）。
- 多人合作：多玩家共享资源，使用博弈 DP + 纳什均衡。
- 强化学习：用 DQN 学习”在资金 K、剩余天数 T 时选哪种作物”，DP 提供教师信号。
八、结语
开心农场把”种田”玩成了”投资组合优化”——这正是动态规划的拿手好戏：把全局最优问题拆成”每天的最优决策 + 未来期望”，由后向前递推。读者可基于本文源码加入更复杂的作物事件、季节系统、好友偷菜逻辑，体验算法在休闲游戏中的真实威力。
