//动态规划法求解整数拆分
//q(i,j)表示用不大于j的整数拆分i
//当i或j==1时,q(i,j)=1;
//当i<j时,q(i,j)=q(i,j-1);
//当i=j,q(i,j)=1+q(i,j-1);
//当i>j,q(i,j)=q(i-j,j)+q(i,j-1);
#include<iostream>
using namespace std;
#define max 10
int q[max][max];
void list(int n, int k)
{
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= k;j++)
{
if (i == 1 || j == 1)
{
q[i][j] = 1;
}
else if (i < j)
{
q[i][j] = q[i][i];
}
else if (i > j)
{
q[i][j] = q[i][ j - 1] + q[i - j][ j];
}
else
q[i][j] = 1 + q[i][ j - 1];
}
}
}
int main()
{
int n, k;
cin >>n >>k;
memset(q, 0, sizeof(q));
list(n, k);
cout << q[n, k] << endl;
}
在输出 q[n, k] 的地方,应该使用数组下标运算符 [] 而不是使用逗号。修改为 q[n][k] 试一下
递归问题:1:一个问题可以分为若干个子问题
2:某些子问题是原子的,另外一些子问题与原问题的逻辑相同
典型的有汉诺塔问题,求阶乘等
**注:**然而对于一个问题,能用循环就不用递归(前提是循环结构实现起来比较简单)
递归问题的本质实质就是对栈的使用。
递归结构:
public Status digui(参数0,1,2…){
if(终止条件){
return;
}
逻辑处理(原子,可以存在也可以不存在)
//递归调用
digui(参数0,1,2…);
逻辑处理(原子,可以存在也可以不存在)
}
对于本题递归时从链表的末尾进行翻转,依次向前
代码实现
public ListNode reverseList(ListNode head) {
//终止条件当前为空或者下一节点为空
if (head == null || head.next == null)
return head;
//递归调用,找到链表末尾
ListNode current = reverseList(head.next);
//对节点进行翻转
ListNode temp = head.next;
temp.next = head;
//此时head表示链表的最后一个节点,应指向null
head.next = null;
return current;
}
若有相同请联系我更改