动态规划经典题解：按摩师、打家劫舍、删除点数与粉刷房子

1. 按摩师

算法原理

1. 确定状态表示
   • dp[i] 表示：选择到 i 位置的时候，此时的最长预约时长 分析细节： 当面对一个预约的时候，可能必选（f），也可能必不选（g）
   • f[i] 表示：选择到 i 的时候，nums[i] 必选，此时的最长预约时长
   • g[i] 表示：选择到 i 的时候，nums[i] 不选，此时的最长预约时长
2. 状态转移方程
   • i-1 选，g[i] = f[i-1]
   • i-1 不选，g[i] = g[i-1]
   • 所以 g[i] = max(f[i-1], g[i-1]) 当 i 不选的时候，那么 i-1 可以选也可不选。 当 i 必选的时候，那么 i-1 就是必不选，此时 f[i] = g[i-1] + nums[i]
3. 初始化
   • 直接初始化 f[0] = nums[0]；g[0] = 0
4. 填表顺序
   • 从左往右，两个表一起填
5. 返回值
   • 最终结果要么是最后一个位置选，要么就是不选
   • 返回 max(f[n-1], g[n-1])

代码编写

public int massage(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // 处理边界条件
    int[] f = new int[n];
    int[] g = new int[n];
    f[0] = nums[0];
    for (int i  ; i < n; i++) {
        f[i] = g[i - ] + nums[i];
        g[i] = Math.max(f[i - ], g[i - ]);
    }
     Math.max(g[n - ], f[n - ]);
}