问题是这样的：

你有 n 级台阶要爬。您一次只能爬 1 或 2 级台阶。找出到达第 N 步的方法数。

解被描述为 t(n) = t(n-1) + t(n-2)。

我一直在想为什么不添加一个常数 2 来表示 t(n-1) 和 t(n-2) 的最后一两步？我直觉上有困难，为什么不在每个阶段添加它？

问题是 t(n-1) 和 t(n-2) 的总和，但我觉得它在哪里解释了向后退一两步的原因？

因为有两个选项，并且您尚未在 t(n-1) 或 t(n-2) 处执行两个步骤，所以不应该在每个步骤中添加一个常数吗？我该如何概念化这个？

我正在尝试解决leetcode 中的Ones 和 Zeros问题，对于相同的代码，但使用向量占用的内存比使用相同大小的数组多约 3 倍。这是我使用 3-D 矢量的代码：

int findMaxForm(vector<string>& strs, int m, int n) {
    int S = strs.size();
    vector<vector<vector<int>>> dp(S+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));

    // int dp[S+1][m+1][n+1];
    // memset(dp, 0, sizeof dp);
    
    for(int i = 0; i < S; i++) {
        for(int j = 0; j <= m; j++) {
            for(int k = 0; k <= n; k++) {
                if(i == 0) {
                    int zeros = count(strs[i].begin(), strs[i].end(), '0');
                    int ones = strs[i].length() - zeros;

                    if(zeros <= …

到目前为止，我的知识是 C 和 CPP/C++ 中的数组具有固定大小。然而最近我遇到了两段代码，这似乎与这个事实相矛盾。我在这里附上照片。想听听每个人对这些如何运作的想法。这里也贴一下代码和疑惑：

1.

#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    char str1[]="Good"; //size of str1 should be 5
    char str2[]="Afternoon";  //size of str2 should be 10
    
    cout<<"\nSize of str1 before the copy: "<<sizeof(str1);
    cout<<"\nstr1: "<<str1;
    
    strcpy(str1,str2);     //copying str1 into str2      
    
    cout<<"\nSize of str1 after the copy: "<<sizeof(str1);
    cout<<"\nstr1: "<<str1;

    return 0;
}

your text O/P： 复制前 str1 的大小：5 str1：良好 复制后 str1 的大小：5 str1：下午

在第一个片段中，我使用 strcpy 将“Afternoon”的 char str2[] 内容复制到 char str1[] 中，其大小比 str2 的大小小 …

问题陈述可以在这里找到.它说DP解决方案需要O(m*n)时间.但为什么我们需要DP呢？我写了以下解决方案,但不确定是否需要DP.

    String str1,str2;
    str1 = "OldSite:GeeksforGeeks.org";
    str2 = "NewSite:GeeksQuiz.com";

    int i,j,k;
    int count,currentMax =0;
    for(i = 0; i < str1.length();i++){
        count = 0;
        k = i;
        for(j = 0; j < str2.length() && k < str1.length();j++){
            if(str1.charAt(k) == str2.charAt(j)){
                count++;
                k++;
            }
            else if(count > currentMax)
                    currentMax = count;
            continue;
        }
        if(count > currentMax)
            currentMax = count;
    }

    System.out.println(currentMax);

即使我的解决方案需要O(m*n),但我似乎没有采用DP方式.

我所做的是检查string1中的每个字符,字符串2中可用的最大长度是多少.

基本上我认为这是蛮力方法.

我的解决方案有什么问题吗？

编辑在评论部分提到.

进行更改以产生正确的结果,将内部for循环更改为

for(j = 0; j < str2.length() && k < str1.length();j++){ …

我试图获得两个字符串的最长公共子序列的长度.它适用于大多数输入,但它会针对指定的输入崩溃.代码如下:

#include <cmath>
#include <string>

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
    return (a > b)? a : b;
}

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(string &X, string &Y, int m, int n )
{
    int L[5000 + 1][5000 + 1] = {0};
    int i, j;

    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
      that …

如何在具有日期类型的字段中显示当前日期和时间.我可以用today()显示当前日期,但是如何显示当前时间.此外,我想在一个领域显示这两个.

谢谢你的帮助.费利克斯

我发现动态编程有点技巧性和要求。但是由于我希望自己成为一名合格的软件工程师，所以我想知道DP会在哪些开发场景中大量使用，或者换句话说，在基于现代计算机的开发中是否有实际用途？

如果您考虑在 spring 框架中广泛使用的代理模式和动态代理等设计模式，DP 似乎只在技术面试中有用。

此外，并行计算和分布式系统的应用似乎并不容易在现代计算机环境中赋能 DP。

是否有一些不罕见的场景，DP 以非常实用的方式被广泛使用？请原谅我的无知，因为我没有在真正的生产级开发中遇到DP，这让我怀疑深入DP的意义。

我正在实现一个函数来计算第 n 个加泰罗尼亚数字。序列的公式如下：

我注意到记忆的解决方案比正常的递归解决方案慢。这是我的代码：

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


int catalan_number_recursive(int n){
    if (n == 0) return 1;

    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
        }

        return ans;
    }
}

int catalan_number_memo(int n, map<int, int> memo){
    memo[0] = memo[1] = 1;


    if (memo.count(n) != 0){
        return memo[n];
    }
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_memo(i, memo)*catalan_number_memo(n …

我正在解决来自 hackerrank 的Sam 和子串问题。它基本上是查找具有所有整数的字符串的所有子字符串的总和。

\n

萨曼莎和山姆正在玩数字游戏。给定一个数字作为字符串，没有前导零，确定该字符串的子字符串的所有整数值的总和。

\n

\n

给定一个字符串形式的整数，将其所有转换为整数的子字符串相加。由于数字可能会变大，因此返回模 10\xe2\x81\xb9\xc2\xa0+\xc2\xa07 的值。

\n

\n

例子：n = \'42\'

\n

\n

这里n是一个字符串，它具有三个整数子字符串：4、2 和 42。它们的和是 48，48 模 10\xe2\x81\xb9\xc2\xa0+\xc2\xa07 = 48。

\n

功能说明

\n

在下面的编辑器中完成 substrings 函数。\nsubstrings 具有以下参数:\nstring n: 整数的字符串表示形式\n返回

\n

int： n中所有子字符串的整数值之和，模 (10\xe2\x81\xb9 + 7)

我尝试使用记忆化来遵循递归自上而下的动态问题解决方案：

from functools import cache\n\ndef substrings(n):\n    @cache\n    def substrSum(curIndex):\n        if curIndex == 0: return int(n[0])\n        return substrSum(curIndex-1)*10 + int(n[curIndex]) * (curIndex+1)\n        \n    totalSum = …

我在一次采访中被问到这个问题。

给定一个表示车轮总数的整数，以及无限供应的两轮和四轮车辆，有多少种方法可以组成一个车队，使得车辆的车轮总数正好是给定的。当且仅当它们包含不同数量的两轮和四轮车辆时，两种选择车辆的方式被认为是不同的。

例如，如果输入数组是[4, 5, 6]，则应返回[2, 0, 2]。个别情况下，我们可以有 1 辆四轮车或 2 辆两轮车有 4 个轮子。我们不能有 5 个轮子。在最后的情况下，我们可以有 1 个四轮和 1 个两轮，或 3 个两轮。

我的解决方案很简单：给定轮子，形成车队的方法数量dp[i] = dp[i - 2] + dp[i - 4]在哪里。dp[i]i

但它没有通过测试用例。我做错了什么？

这是DP中一个非常著名的问题，有人可以帮助可视化它的递归部分吗？排列或组合将如何生成。

问题参考。 https://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/

我遇到过这样的算法问题

给定一个包含 N 个元素的数组，我想找到数组中 k 个元素的最大偶数和

例如：

A = [4,2,6,7,8], K = 3, 算法应该返回 18 为 4 + 6 + 8 = 18

A = [5, 5, 2, 4, 3], K = 3, 算法应该返回 14 为 5 + 5 + 4 = 14

非常感谢您的帮助。

我尝试使用10 ^ 6乘10 ^ 6阵列,它给我分段故障