Epam | OAMaster

01Rob Houses Without Getting Caught

You are a robber and you need to rob houses, the number of houses you need to rob are denoted by y and total number of houses that are there are denoted by n. You must not get caught and rob y houses, to not get caught, the total distance you travelled should be a multiple of an integer denoted by x. The array a is given where a[i] denotes the distance between two houses. You cannot rob the house you have already robbed and you can start from anywhere to start robbing. Return the total number of ways you can rob houses without getting caught.

Constraints

N/A

Example 1

Input:

n = 4
y = 3
x = 6
a = [4, 3, 5]

Output:

Explanation: The possible ways to rob houses without getting caught, where the total distance travelled is a multiple of x are:

1->2->4 with a total distance of 4+3+5 = 12, which is a multiple of 6.
1->3->4 with a total distance of 4+5+3 = 12, which is a multiple of 6.
4->2->1 with a total distance of 5+3+4 = 12, which is a multiple of 6.
4->3->1 with a total distance of 5+4+3 = 12, which is a multiple of 6. Therefore, there are 4 ways to rob the houses without getting caught.

解法

DP 计算"在余下数组中选恰好 y 个、总距离模 x 为 0"的方案数。dp[i][j][r] 表示考虑前 i 个间距、已选 j 个、当前和模 x 为 r 的方案数。转移：选或不选 a[i]。最终所有方向都对应同一选择(每条路径正反算两次)，答案乘以方向数 2 再调整。注意题面允许从任一端开始且方向影响顺序。时间 O(n·y·x)，空间 O(y·x)。

from typing import List

def rob_houses(n: int, y: int, x: int, a: List[int]) -> int:
    m = len(a)
    # dp[j][r] = # ways to choose j gaps with sum % x == r
    dp = [[0] * x for _ in range(y + 1)]
    dp[0][0] = 1
    for d in a:
        for j in range(min(y, m), 0, -1):
            for r in range(x):
                pr = (r - d) % x
                dp[j][r] += dp[j - 1][pr]
    base = dp[y][0]
    # Each ordered route corresponds to a chosen multiset of gaps; routes can be reversed and started from either end ⇒ multiply by 2 if y >= 1
    return base * 2 if y >= 1 else base

class Solution {
    public long robHouses(int n, int y, int x, int[] a) {
        long[][] dp = new long[y + 1][x];
        dp[0][0] = 1;
        for (int d : a) {
            for (int j = Math.min(y, a.length); j >= 1; j--) {
                for (int r = 0; r < x; r++) {
                    int pr = ((r - d) % x + x) % x;
                    dp[j][r] += dp[j - 1][pr];
                }
            }
        }
        long base = dp[y][0];
        return y >= 1 ? base * 2 : base;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long robHouses(int n, int y, int x, vector<int>& a) {
        vector<vector<long long>> dp(y + 1, vector<long long>(x, 0));
        dp[0][0] = 1;
        for (int d : a) {
            for (int j = min(y, (int)a.size()); j >= 1; j--) {
                for (int r = 0; r < x; r++) {
                    int pr = ((r - d) % x + x) % x;
                    dp[j][r] += dp[j - 1][pr];
                }
            }
        }
        long long base = dp[y][0];
        return y >= 1 ? base * 2 : base;
    }
};