Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में कुछ चरणों के बाद उसी स्थान पर रहने के तरीकों की संख्या

मान लीजिए arrLen आकार की एक सरणी है, और हमारे पास उस सरणी में इंडेक्स 0 पर एक पॉइंटर है। प्रत्येक चरण में, हम सरणी में 1 स्थिति बाएं, 1 स्थिति दाएं जा सकते हैं या उसी स्थान पर रह सकते हैं।

अब मान लीजिए हमारे पास दो पूर्णांक steps और arrLen हैं, हमें उन तरीकों की संख्या ज्ञात करनी है जैसे कि पॉइंटर ठीक steps के बाद इंडेक्स 0 पर ही रहे। यदि उत्तर बहुत बड़ा है तो इसे मॉड्यूलो 10^9 + 7 पर लौटाएं।

यदि इनपुट steps = 3, arrLen = 2 है, तो आउटपुट 4 होगा, क्योंकि 3 चरणों के बाद इंडेक्स 0 पर रहने के 4 अलग-अलग तरीके हैं। ये हैं [दाएं, बाएं, रहें], [रहें, दाएं, बाएं], [दाएं, रहें, बाएं], [रहें, रहें, रहें]।

हल करने के चरण

  • m := 10^9 + 7

  • add() फ़ंक्शन परिभाषित करें: (a % m + b % m) % m लौटाएं

  • एक 2D सरणी dp परिभाषित करें

  • solve() फ़ंक्शन परिभाषित करें जो n, x, pos (0 से आरंभ) लेता है

  • यदि x == 0 तो pos == 0 होने पर true लौटाएं

  • यदि dp[pos][n] != -1 तो dp[pos][n] लौटाएं

  • ans := 0, यदि pos > 0 तो ans = add(ans, solve(n, x-1, pos-1))

  • यदि pos < n-1 तो ans = add(ans, solve(n, x-1, pos+1))

  • ans = add(ans, solve(n, x-1, pos)), dp[pos][n] = ans, ans लौटाएं

  • मुख्य विधि से: x = min(arrLen, steps/2 + 1), dp आरंभ करें, पुनरावर्ती DP से उत्तर की गणना करें

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
typedef long long int lli; 
const int MOD = 1e9 + 7; 

lli add(lli a, lli b) { 
    return (a % MOD + b % MOD) % MOD; 
} 

class Solution { 
public: 
    vector<vector<int> > dp; 
    int solve(int n, int x, int pos = 0) { 
        if (x == 0) return pos == 0; 
        if (dp[pos][n] != -1) return dp[pos][n]; 
        int ans = 0; 
        if (pos > 0) ans = add(ans, solve(n, x - 1, pos - 1)); 
        if (pos < n - 1) ans = add(ans, solve(n, x - 1, pos + 1)); 
        ans = add(ans, solve(n, x - 1, pos)); 
        dp[pos][n] = ans; 
        return ans; 
    } 
    int numWays(int steps, int arrLen) { 
        int x = min(arrLen, steps / 2 + 1); 
        this->dp = vector<vector<int> >(2, vector<int>(x + 1, 0)); 
        dp[0][0] = 1; 
        int n = arrLen; 
        for (int i = 1; i <= steps; i++) { 
            for (int j = 0; j < min(arrLen, steps / 2 + 1); j++) { 
                int x = (i - 1) % 2; 
                int y = i % 2; 
                dp[y][j] = dp[x][j]; 
                if (j - 1 >= 0) dp[y][j] = add(dp[y][j], dp[x][j - 1]); 
                if (j + 1 < n) dp[y][j] = add(dp[y][j], dp[x][j + 1]); 
            } 
        } 
        return dp[steps % 2][0]; 
    } 
}; 

int main() { 
    Solution ob; 
    cout << (ob.numWays(3, 2)); 
    return 0; 
}

इनपुट

3, 2

आउटपुट

4
  1. C++ में N-ary ट्री को पार करने के तरीकों की संख्या C++ में N-ary ट्री को पार करने के तरीकों की संख्या

    एक N-ary ट्री दिया गया है और हमें इस ट्री को पार करने के कुल तरीकों की संख्या निकालने का कार्य दिया गया है, उदाहरण के लिए -उपरोक्त ट्री के लिए, हमारा आउटपुट 192 होगा।इस समस्या के लिए, हमें कॉम्बिनेटोरिक्स के बारे में कुछ ज्ञान होना चाहिए। अब इस समस्या में, हमें बस हर पथ के लिए सभी संभावित संयोजनों क

  1. C++ में n x m आकार के फर्श को 1 x m टाइलों से टाइल करने के तरीकों की संख्या गिनें C++ में n x m आकार के फर्श को 1 x m टाइलों से टाइल करने के तरीकों की संख्या गिनें

    समस्या विवरण दो संख्याएं n और m दी गई हैं जो कमरे के फर्श की लंबाई और चौड़ाई दर्शाती हैं। लक्ष्य उन तरीकों की संख्या गिनना है जिनसे इस फर्श को 1xm आकार की टाइलों का उपयोग करके टाइल किया जा सकता है। उदाहरण इनपुट n=3 m=2 आउटपुट फर्श को टाइल करने के तरीकों की संख्या: 3 व्याख्या तीन 1x2 टाइलें नीचे दि

  1. C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम

    परिचय मान लीजिए हमारे पास ट्री एजेज की एक सूची है [u, v] के रूप में, जो इंगित करती है कि u और v के बीच एक अनडायरेक्टेड एज है। और हमारे पास दो मान x और y भी हैं। यदि हम नोड x पर हैं, और हमारा प्रतिद्वंद्वी नोड y पर है। पहले राउंड में हम चलते हैं, फिर अगले राउंड में प्रतिद्वंद्वी चलता है और इसी तरह।