动态规划入门与状态设计

from functools import cache


def num_decodings(s: str) -> int:
    """Ways to read a digit string as letters, 1 = A ... 26 = Z (LC 91)."""

    @cache
    def ways(i: int) -> int:  # ways to decode s[i:]
        if i == len(s):
            return 1
        if s[i] == "0":
            return 0  # no letter's code starts with 0
        total = ways(i + 1)  # read one digit
        if i + 1 < len(s) and int(s[i : i + 2]) <= 26:
            total += ways(i + 2)  # or two
        return total

    return ways(0)

// Ways to read a digit string as letters, 1 = A ... 26 = Z (LC 91).
long long numDecodings(const string& s) {
    int n = s.size();
    vector<long long> memo(n + 1, -1);  // memo[i]: ways to decode s[i..], -1 = not computed yet
    function<long long(int)> ways = [&](int i) -> long long {
        if (i == n) return 1;
        if (memo[i] >= 0) return memo[i];
        if (s[i] == '0') return memo[i] = 0;  // no letter's code starts with 0
        long long total = ways(i + 1);  // read one digit
        if (i + 1 < n && stoi(s.substr(i, 2)) <= 26) total += ways(i + 2);  // or two
        return memo[i] = total;
    };
    return ways(0);
}

class Solution {
    private Long[] memo; // memo[i]: ways to decode s[i..], null = not computed yet
    private String s;

    // Ways to read a digit string as letters, 1 = A ... 26 = Z (LC 91).
    long numDecodings(String s) {
        this.s = s;
        memo = new Long[s.length() + 1];
        return ways(0);
    }

    private long ways(int i) {
        if (i == s.length()) return 1;
        if (memo[i] != null) return memo[i];
        long total = 0;
        if (s.charAt(i) != '0') { // no letter's code starts with 0
            total = ways(i + 1); // read one digit
            if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26) total += ways(i + 2); // or two
        }
        return memo[i] = total;
    }
}

// numDecodings returns the ways to read a digit string as letters, 1 = A ... 26 = Z (LC 91).
func numDecodings(s string) int {
	n := len(s)
	memo := make([]int, n+1) // memo[i]: ways to decode s[i:], -1 = not computed yet
	for i := range memo {
		memo[i] = -1
	}
	var ways func(i int) int
	ways = func(i int) int {
		if i == n {
			return 1
		}
		if memo[i] >= 0 {
			return memo[i]
		}
		total := 0
		if s[i] != '0' { // no letter's code starts with 0
			total = ways(i + 1) // read one digit
			if i+1 < n && (s[i]-'0')*10+(s[i+1]-'0') <= 26 {
				total += ways(i + 2) // or two
			}
		}
		memo[i] = total
		return total
	}
	return ways(0)
}

def rob_circle(nums: list[int]) -> int:
    """House robber with the houses in a circle: the first and last are neighbours (LC 213)."""

    def rob_line(lo: int, hi: int) -> int:  # the plain robber on nums[lo:hi]
        prev2 = prev1 = 0
        for x in nums[lo:hi]:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1

    if len(nums) == 1:
        return nums[0]
    return max(rob_line(0, len(nums) - 1), rob_line(1, len(nums)))  # without the last, or without the first

// House robber with the houses in a circle: the first and last are neighbours (LC 213).
int robCircle(const vector<int>& nums) {
    auto robLine = [&](int lo, int hi) {  // the plain robber on nums[lo, hi)
        int prev2 = 0, prev1 = 0;
        for (int i = lo; i < hi; i++) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    };
    int n = nums.size();
    if (n == 1) return nums[0];
    return max(robLine(0, n - 1), robLine(1, n));  // without the last, or without the first
}

class Solution {
    // House robber with the houses in a circle: the first and last are neighbours (LC 213).
    int robCircle(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLine(nums, 0, n - 1), robLine(nums, 1, n)); // without the last, or without the first
    }

    // The plain robber on nums[lo, hi).
    private int robLine(int[] nums, int lo, int hi) {
        int prev2 = 0, prev1 = 0;
        for (int i = lo; i < hi; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

// robCircle is the house robber with the houses in a circle: the first and last are neighbours (LC 213).
func robCircle(nums []int) int {
	robLine := func(line []int) int { // the plain robber on a line of houses
		prev2, prev1 := 0, 0
		for _, x := range line {
			prev2, prev1 = prev1, max(prev1, prev2+x)
		}
		return prev1
	}
	n := len(nums)
	if n == 1 {
		return nums[0]
	}
	return max(robLine(nums[:n-1]), robLine(nums[1:])) // without the last, or without the first
}