# dp[!t][val] for skipping the parts from array

#### Tags: c++, dynamic-programming, java, knapsack-problem

consider the following snippet in cpp. This is taken from dynamic programming tutorial .

It is mainly for space optimized knapsack problem.

```for(int i=1;i<=a;i++)
{
int t = a%2;
for(int j=0;j<1100000;j++) dp[t][j]  = inf;
for(int j=0;j<1100000;j++){
dp[t][j] = min(dp[t][j],dp[!t][j-v[i-1]]+w[i-1]);//!t part is for skipping the current
}
}
```

This snippet is taken from this tutorial. I want to convert this technique into java. But java does not support this type of integer manipulation. Please can anyone explain me how it works and appropriate conversion to java ? thanks.

Just replace `!t` with `t ^ 1` or `1 - t` (whatever you find more readable; the effect is the same). That’s all you need to do here.

## Explanation

Java supports all the integer manipulation on display in this snippet:

`int t = a % 2;` <– this is valid java and means the same thing in java as it does in C: divide a by 2, and put the remainder in t, preserving the sign of `a`. Thus: `t` is now 0 if `a` was even, and `1` if a was positive and odd, and `-1` if a was negative and odd. It looks like `a` is supposed to be positive in this scenario, meaning that `t` can only be `0` or `1` here.

`dp[t][j]` <– valid java. Declare `dp` as for example `int[][] dp = new int;`.

`min(someExpression, someOtherExpression)` <– valid java; add `import static java.lang.Math.min;` or replace min with `Math.min` to make it work.

`dp[!t]` <– the `!t` isn’t valid java; but, in C, running `!t` where `t` is either 0 or 1 is just flipping things: If `t` is 1, `!t` is 0, and vice versa. And that you can trivially do in java: Use `t ^ 1` or `1 - t` or even `t == 0 ? 1 : 0` – all have the exact same behaviour and are valid java.

Source: stackoverflow