#java #dynamic-programming
Вопрос:
Учитывая массив целых чисел, нам нужно подсчитать его подпоследовательности, следующие заданному условию:
- давайте i1, i2, i3…iN являются индексами данного массива, а Ai1, Ai2, Ai3….AiN являются соответствующими элементами. X-целое число; N длина массива; A-массив;
- Подсчитайте всю подпоследовательность, имеющую (Ai1^Ai2^Ai3^…^AiN)amp;X == 0;
// A = [5,3,7], N = 3, X = 1
// Now there are 2 pow 3 subsequences are there
// consider empty array is also a subsequence
public long count(int[] A, int N, int X){
}
Комментарии:
1. Какой подход вы пробовали ?
2. Я попробовал стандартное решение для подсчета подпоследовательности, но как сохранить предыдущий результат? Это не так просто, как строка или никакого сравнения. Где мы делаем dp[i] = 2*dp[i-1], а после этого проверяем карту и вычитаем те же события.
3. Каково максимальное значение X и N?
4. для X возьмите любое значение, большее или равное 1, и я забыл о N, но возьмите 10^5