- 给定一个正数1，裂开的方法有一种，(1) 给定一个正数2，裂开的方法有两种，(1和1)、(2) 给定一个正数3，裂开的方法有三种，(1、1、1)、(1、2)、(3) 给定一个正数4，裂开的方法有五种，(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、 (4)
给定一个正数n，求裂开的方法数。 动态规划优化状态依赖的技巧 - 注意裂开时后一种方法不能小于前一种。
/**
* 给定一个正数1，裂开的方法有一种，(1) 给定一个正数2，裂开的方法有两种，(1和1)、(2)
* 给定一个正数3，裂开的方法有三种，(1、1、1)、(1、2)、(3) 给定一个正数4，
* 裂开的方法有五种，(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、 (4)
* 给定一个正数n，求裂开的方法数。 动态规划优化状态依赖的技巧
*/
public class SplitWaysNum {
// 暴力递归
public static int splitWaysNum(int n){
if(n <= 0){
return 0;
}
// 不能比1小
return process(1,n);
}
// 递归含义：
// pre 前一次裂开的值，rest:当前还可以裂开的值
private static int process(int pre,int rest){
if(rest == 0){
// 如果已经没有可以裂开的值了，表示前面的方案有效
return 1;
}
// 如果pre > 剩下的可以裂开的值，那么这种方案不行，0种方案
if(pre > rest){
return 0;
}
// rest不为0，且pre 也不大于rest
// 枚举rest每一种的裂开方式
int ways = 0;
for (int i = pre; i <= rest; i++) {
// i必须大于等于pre
ways += process(i,rest-i);
}
return ways;
}
// 动态规划
public static int dp(int n){
if(n <= 0){
return 0;
}
int[][] dp = new int[n+1][n+1];
// 第1行无效，因为pre至少从1开始
for (int i = 1; i < dp.length; i++) {
dp[i][0] = 1;
}
// pre > rest 全为0
for (int pre = dp.length-1; pre >= 1; pre--) {
for (int rest = pre; rest < dp[0].length ; rest++) {
int ways = 0;
for (int i = pre; i <= rest; i++) {
// i必须大于等于pre
ways += process(i,rest-i);
}
dp[pre][rest] = ways;
}
}
return dp[1][n];
}
// 动态规划(省去枚举行为)
public static int dp2(int n){
if(n <= 0){
return 0;
}
int[][] dp = new int[n+1][n+1];
// 第1行无效，因为pre至少从1开始
for (int i = 1; i < dp.length; i++) {
dp[i][0] = 1;
}
// pre > rest 全为0
for (int pre = dp.length-1; pre >= 1; pre--) {
for (int rest = pre; rest < dp[0].length ; rest++) {
dp[pre][rest] = dp[pre][rest-pre] + (pre + 1 < dp.length ? dp[pre+1][rest] : 0);
}
}
return dp[1][n];
}
public static void main(String[] args) {
System.out.println(splitWaysNum(23));
System.out.println(dp(23));
System.out.println(dp2(23));
}
}
- 给定一个整数N，代表你有1～N这些数字。在给定一个整数K。你可以随意排列这些数字，但是每一种排列都有若干个逆序对。返回有多少种排列，正好有K个逆序对
例子1:
Input: n = 3, k = 0
Output: 1
解释：
只有[1,2,3]这一个排列有0个逆序对。
例子2:
Input: n = 3, k = 1
Output: 2
解释
[3,2,1]有(3,2)、(3,1)、(2,1)三个逆序对，所以不达标。
达标的只有：
[1,3,2]只有(3,2)这一个逆序对，所以达标。
[2,1,3]只有(2,1)这一个逆序对，所以达标。
/**
* 给定一个整数N，代表你有1～N这些数字。在给定一个整数K。你可以随意排列这些数字，
* 但是每一种排列都有若干个逆序对。返回有多少种排列，正好有K个逆序对
*
* 例子1:
* Input: n = 3, k = 0
* Output: 1
* 解释：
* 只有[1,2,3]这一个排列有0个逆序对。
*
* 例子2:
* Input: n = 3, k = 1
* Output: 2
* 解释
* [3,2,1]有(3,2)、(3,1)、(2,1)三个逆序对，所以不达标。
* 达标的只有：
* [1,3,2]只有(3,2)这一个逆序对，所以达标。
* [2,1,3]只有(2,1)这一个逆序对，所以达标。
*/
public class ReverseNum {
// 动态规划
public static int reverseNum(int n,int k){
if(n <= 0 || k < 0){
return 0;
}
// 1~n,0~k
// n作为行，k作为列
int[][] dp = new int[n+1][k+1];
// 第一行,n=0,n>0舍弃
// 第一行，只有第一个位置是1，代表只有一个数字，搞出0个逆序对，其他全是0
dp[1][0] = 1;
// 第一列，dp[i][0] i > 0,表示有1~一个数字搞出0个逆序对，只有一种方法
for (int i = 1; i <= n; i++) {
dp[i][0] = 1;
}
// 普遍位置的依赖关系
// dp[7][4]，1~7的数字形成的逆序对刚好是4个有多少种排列方法
// 以7的位置来划分:
// 1.如果7放在排列的最后一个数字，那么他可以形成0个逆序对，则需要1~6形成4个逆序对
// 2.如果7放在倒数第二个位置，那么他可以形成，1个逆序对，需要1~6形成3个逆序对
// 3.如果7放在倒数第三个位置，。。。。。。。。2个。。。。。。1~6 2个
// 4.如果7 四。。。。。。。。。。。 3 1个
// 5. 7 五 4 0个
// 注意： 7放在第六个位置逆序对个数就超过4了，不达标
// => dp[7][4] = dp[6][4]+dp[6][3] + dp[6][2] + dp[6][1]+dp[6][0]
//如果是i<=j呢。比如dp[7][9]
// dp[7][9] == dp[6][9] + dp[6][8] + ....7.6,5,4,3
// 到不了0
for (int i = 2; i <= n ; i++) {
for (int j = 1; j <= k ; j++) {
for(int h = j; h >= Math.max(0,j-i+1);h--){
dp[i][j] += dp[i-1][h];
}
}
}
return dp[n][k];
}
public static int dp(int n,int k){
if(n <= 0 || k < 0){
return 0;
}
// 1~n,0~k
// n作为行，k作为列
int[][] dp = new int[n+1][k+1];
// 第一行,n=0,n>0舍弃
// 第一行，只有第一个位置是1，代表只有一个数字，搞出0个逆序对，其他全是0
dp[1][0] = 1;
// 第一列，dp[i][0] i > 0,表示有1~一个数字搞出0个逆序对，只有一种方法
for (int i = 1; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 2; i <= n ; i++) {
for (int j = 1; j <= k ; j++) {
// if(i > j){
// dp[i][j] = dp[i-1][j] + dp[i][j-1];
// }
// if(j >= i){
// dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-i];
// }
// 画图，看依赖关系
dp[i][j] = dp[i-1][j] + dp[i][j-1] - (j >= i ? dp[i-1][j-i] : 0);
}
}
return dp[n][k];
}
public static void main(String[] args) {
int n = 11;
int k = 5;
System.out.println(reverseNum(n,k));
System.out.println(dp(n,k));
}
}
