একটি লিস্ট nums এবং একটি মান k দেওয়া আছে। আকার k-এর স্ট্রিক্টলি ইনক্রিজিং সাবসিকোয়েন্স কতটি আছে সেটি বের করতে হবে। উত্তর বড় হলে 10^9+7 দিয়ে মড করুন।
উদাহরণস্বরূপ, nums = [2, 3, 4, 1], k = 2 হলে আউটপুট ৩: [2,3], [3,4], [2,4]।
সমাধানের পদ্ধতি (DP)
m = 10**9 + 7।dp= আকারlen(nums), সব ১ (দৈর্ঘ্য ১-এর সাবসিকোয়েন্স)।k-1বার ইটারেট করুন (দৈর্ঘ্য ২ থেকে k পর্যন্ত বানাতে):j= n-1 থেকে ০ পর্যন্ত (উল্টা দিক থেকে):dp[j] = 0।i = 0..j-1: যদিnums[i] < nums[j],dp[j] = (dp[j] + dp[i]) % m।
sum(dp) % mরিটার্ন করুন।
পাইথন কোড উদাহরণ
class Solution:
def solve(self, nums, k):
m = 10**9 + 7
dp = [1] * len(nums)
for _ in range(k - 1):
for j in range(len(dp) - 1, -1, -1):
dp[j] = 0
for i in range(j):
if nums[i] < nums[j]:
dp[j] = (dp[j] + dp[i]) % m
return sum(dp) % m
ob = Solution()
nums = [2, 3, 4, 1]
k = 2
print(ob.solve(nums, k))ইনপুট
[2, 3, 4, 1], 2
আউটপুট
3
