动态规划(DP)记忆化：如何确定递归的起始位置？

刚接触算法编程测试，常会困惑记忆化递归的起始位置该选0还是数组长度n。下面结合两个经典问题拆解规律：

1. 最小花费爬楼梯 #

题目描述 #

给你一个整数数组 cost，其中 cost[i] 是楼梯第 i 个台阶的花费。一旦你支付此花费，你可以选择爬1级或2级台阶。
你可以从下标为0或1的台阶开始爬。
返回到达楼梯顶部的最小花费。

递推关系式 #

minimumCost(i) = min(cost[i - 1] + minimumCost(i - 1), cost[i - 2] + minimumCost(i - 2))

记忆化递归代码 #

int rec(int n, vector<int>& cost)
{
    if(memo[n] == -1)
    {
        if(n <= 1)
        {
            memo[n] = 0;
        } else
        {
            memo[n] = min(rec(n-1, cost) + cost[n-1], rec(n-2, cost) + cost[n-2]);
        }
    }
    return memo[n];
}

int minCostClimbingStairs(vector<int>& cost) {
    const int n = cost.size();
    memo.assign(n+1,-1);
    return rec(n, cost); // 从n开始递归
}

2. 打家劫舍 #

题目描述 #

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

递推关系式 #

robFrom(i) = max(robFrom(i + 1), robFrom(i + 2) + nums[i])

记忆化递归代码 #

int getrob(int n, vector<int>& nums)
{
    if(how_much[n] == -1)
    {
        if(n >= nums.size())
        {
            return 0;
        } else {
            how_much[n] = max(getrob(n + 1, nums), getrob(n + 2, nums) + nums[n]);
        }
    }
    return how_much[n];
}

int rob(vector<int>& nums) {
    how_much.assign(nums.size() + 2, -1);
    return getrob(0, nums); // 从0开始递归
}

核心判断规律 #

不用全靠刷题培养直觉，抓住以下两点就能快速判断：

• 明确递归函数的定义：
  先搞清楚你的递归函数f(i)到底代表什么。比如：
  • 最小花费爬楼梯中，rec(n)代表「到达第n个位置（楼梯顶部）的最小花费」，而题目要求的就是这个值，所以直接从n开始递归。
  • 打家劫舍中，getrob(n)代表「从第n间房屋开始偷，能拿到的最大金额」，题目要求从第0间开始偷的最大金额，所以从0开始递归。
• 看递推的依赖方向：
  • 如果f(i)依赖f(i-1)、f(i-2)这类更小的下标，说明需要从大的目标下标往小的初始下标回溯，起始点就是最终的目标位置（比如n）。
  • 如果f(i)依赖f(i+1)、f(i+2)这类更大的下标，说明需要从小的初始下标往大的边界下标推进，起始点就是初始位置（比如0）。

另外，边界条件也能辅助验证：递归起始点要能自然触达边界条件，比如最小花费从n开始会逐步到n<=1的边界，打家劫舍从0开始会逐步到n>=数组长度的边界。

内容的提问来源于stack exchange，提问作者Daniel Kim