整数划分

我不怎么做算法题，今天才碰到整数划分，结果还是个经典递归/dp题目

参考链接给的是递归解法。

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return equationCount(n,n);
    else if(n==m)
        return 1+equationCount(n,n-1);
    else
        return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
    {
        printf("%d\n",equationCount(n,n));
    }
    return 0;
}

递归和DP是一体两面，比如台阶dp

l = []
l.append(0)
l.append(1)
l.append(2)
n=int(input())
for i in range(3,n+1):
    l.append(l[i-1]+l[i-2])

print(l[n])

判断进程

lsof

netstat -tcp closewait

ref

• https://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html

• https://www.zhihu.com/question/56577396 这个问题讲了整数划分的背景

• https://blog.csdn.net/dst111188/article/details/78554698 递归和DP的关系，空间换时间。核心的转换公式都是一样的。

• http://blackblog.tech/2018/08/24/LeetCodeReview6/ 列了一些leetcode上的DP题目的解法。很有心了

• https://blog.csdn.net/sxhelijian/article/details/8978794

• https://blog.csdn.net/sxhelijian/article/details/8978850 上面这两个链接是c/c++输入模板